{"id":43,"date":"2009-11-26T20:26:00","date_gmt":"2009-11-26T12:26:00","guid":{"rendered":"http:\/\/localhost\/?p=43"},"modified":"2009-11-26T20:26:00","modified_gmt":"2009-11-26T12:26:00","slug":"usaco_2005_november_silver","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=43","title":{"rendered":"USACO 2005 November Silver"},"content":{"rendered":"

http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3044<\/a>
http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3045
http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3046
@@@1@@@
\u8003\u8651\u4e00\u5757\u623f\u5b50(\u5c31\u662f\u4e24\u8fb9\u90fd\u662f\u5730\u3002\u3002)
\u90a3\u4e48\u5176\u4e2d\u6700\u77ee\u7684\u4e00\u5757\u7684\u9ad8\u5ea6\u5fc5\u7136\u662f\u8fd9\u4e00\u5757\u4e2d\u6700\u77ee\u7684\u3002\u3002
\u90a3\u4e48\u8d2a\u5fc3\u7684\u9009\u62e9\u81ea\u7136\u662f\u8ba9\u5b83\u53d8\u5f97\u6700\u5bbd\u3002\u3002\u7136\u540e\u518d\u5f80\u4e0a\u642d\u3002\u3002\u3002
\u6211\u76f4\u63a5\u66b4\u529b\u5b9e\u73b0\u4e86\u3002\u3002\u5e73\u5747\u662fO(nlogn)\u3002\u3002\u6700\u574f\u662f\uff2f(n^2)\u3002\u3002\u5e78\u597d\u6570\u636e\u5f88\u539a\u9053\u3002\u3002
\u66b4\u529b\u627e\u6700\u5c0f\u503c\u3002\u3002
\u5b98\u65b9\u7a0b\u5e8f\u53ea\u8981\u6808\u626b\u63cf\u5c31\uff2f\uff2b\u4e86\u3002\u3002\u6211\uff33\uff22\u963f\u3002\u3002
#include<iostream>
#include<cstdio>
using namespace std;
const int maxy=500000,maxn=50000;
int w,n;
int H[maxn];
int cal(int i,int j)
{
if(i>j) return 0;
if(i==j) return H[i]>0;
int c=maxy;
for(int o=i;o<=j;o++)
c=min(H[o],c);
int a=i,ans=0;
for(int o=i;o<=j;o++)
if(H[o]==c)
ans+=cal(a,o-1),a=o+1;
ans+=cal(a,j);
if(c) ans++;
return ans;
}
int main()
{
cin>>n>>w;int x;
for(int i=0;i<n;i++)
{
scanf("%d %d",&x,H+i);
}
cout<<cal(0,n-1)<<endl;
}@@@@2@@@@
\u770b\u4e24\u4e2a\u725bi\u548ci’\u3002\u3002\u8bbe\u4ed6\u4eec\u91cd\u91cf\u548c\u529b\u91cf\u5206\u522b\u4e3aA,B,A’,B’..
\u4ed6\u4eec\u4e0a\u9762\u7684\u725b\u603b\u91cd\u4e3a\uff33
\u5047\u5982A+B>A’+B’\u3000\u90a3\u4e48\u3000A-B’>A’-B
\uff33
\uff21\u3000\uff22
\uff21\u2018\u3000\uff22\u2019
max(S-B,S+A-B’) i\u5728\u4e0a\u9762\u3002\u3002
max(S-B’,S+A’-B) i’\u5728\u4e0a\u9762\u3002\u3002
\u90a3\u4e48\u603b\u662fi’\u5728\u4e0a\u9762\u66f4\u597d\u3002\u3002\u3002
\u540c\u7406\u5982\u679cA+B=A’+B’\u3002\u3002
\u90a3\u4e48\uff22\u5927\u7684\u5728\u4e0a\u9762\u597d\u3002\u3002\u3002
\u76f4\u63a5\u6392\u5e8f\u5c31OK\u4e86\u3002\u3002
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50000,inf=~0U>>1;
int n;
struct node
{
int w,s;
bool operator<(const node&x) const
{
int a=w+s,b=x.w+x.s;
if(a!=b) return a<b;
return w<x.w;
}
}Q[maxn];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d %d",&Q[i].w,&Q[i].s);
}
sort(Q,Q+n);
int Sum=0,ans=-inf;
for(int i=0;i<n;i++)
{
ans=max(ans,Sum-Q[i].s);
Sum+=Q[i].w;
}
cout<<ans<<endl;
}@@@@3@@@@
\u8fd9\u9053\u9898\u8ba9\u6211\u60f3\u5230\u4e86\u6bcd\u51fd\u6570\u3002\u3002
\u7136\u540e\u6211\u5c31\u76f4\u63a5\u4e0a\u6bcd\u51fd\u6570\u4e86\u3002\u3002\u3002
#include<iostream>
using namespace std;
const int maxn=1000,maxl=100000,Mod=1000000;
struct P
{
int *C;
int n;
P(int n):n(n)
{
C=new int[n+1];
for(int i=0;i<=n;i++)
C[i]=1;
}
int& operator[](int v){return C[v];}
void operator*=(P&x)
{
int*now=new int[n+x.n+1];
for(int i=0;i<=n+x.n;i++) now[i]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=x.n;j++)
{
now[i+j]+=C[i]*x[j];
now[i+j]%=Mod;
}
delete[] C;
C=now;n+=x.n;
}
};
int C[maxn]={0};
int T,A,S,B;
int main()
{
cin>>T>>A>>S>>B;
while(A–)
{
int t;cin>>t;
C[t-1]++;
}
P ans(0);
for(int i=0;i<T;i++)
{
P now(C[i]);
ans*=now;
}
int sum=0;
for(int i=S;i<=B;i++)
sum+=ans[i],sum%=Mod;
cout<<sum<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"

http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3044http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3045http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3046@@@1@@@\u8003\u8651\u4e00\u5757\u623f\u5b50(\u5c31\u662f\u4e24\u8fb9\u90fd\u662f\u5730\u3002\u3002)\u90a3\u4e48\u5176\u4e2d\u6700\u77ee\u7684\u4e00\u5757\u7684\u9ad8\u5ea6\u5fc5\u7136\u662f\u8fd9\u4e00\u5757\u4e2d\u6700\u77ee\u7684\u3002\u3002\u90a3\u4e48\u8d2a\u5fc3\u7684\u9009\u62e9\u81ea\u7136\u662f\u8ba9\u5b83\u53d8\u5f97\u6700\u5bbd\u3002\u3002\u7136\u540e\u518d\u5f80\u4e0a\u642d\u3002\u3002\u3002\u6211\u76f4\u63a5\u66b4\u529b\u5b9e\u73b0\u4e86\u3002\u3002\u5e73\u5747\u662fO(nlogn)\u3002\u3002\u6700\u574f\u662f\uff2f(n^2)\u3002\u3002\u5e78\u597d\u6570\u636e\u5f88\u539a\u9053\u3002\u3002\u66b4\u529b\u627e\u6700\u5c0f\u503c\u3002\u3002\u5b98\u65b9\u7a0b\u5e8f\u53ea\u8981\u6808\u626b\u63cf\u5c31\uff2f\uff2b\u4e86\u3002\u3002\u6211\uff33\uff22\u963f\u3002\u3002#include<iostream>#include<cstdio>using namespace std;const int maxy=500000,maxn=50000;int w,n;int H[maxn];int cal(int i,int j){ if(i>j) return 0; if(i==j) return H[i]>0; int c=maxy; for(int o=i;o<=j;o++) c=min(H[o],c); int a=i,ans=0; for(int o=i;o<=j;o++) if(H[o]==c) ans+=cal(a,o-1),a=o+1; ans+=cal(a,j); if(c) ans++; return ans;}int main(){ cin>>n>>w;int x; for(int i=0;i<n;i++) { scanf("%d %d",&x,H+i); } cout<<cal(0,n-1)<<endl;}@@@@2@@@@\u770b\u4e24\u4e2a\u725bi\u548ci’\u3002\u3002\u8bbe\u4ed6\u4eec\u91cd\u91cf\u548c\u529b\u91cf\u5206\u522b\u4e3aA,B,A’,B’..\u4ed6\u4eec\u4e0a\u9762\u7684\u725b\u603b\u91cd\u4e3a\uff33\u5047\u5982A+B>A’+B’\u3000\u90a3\u4e48\u3000A-B’>A’-B\uff33\uff21\u3000\uff22\uff21\u2018\u3000\uff22\u2019max(S-B,S+A-B’) i\u5728\u4e0a\u9762\u3002\u3002max(S-B’,S+A’-B) i’\u5728\u4e0a\u9762\u3002\u3002\u90a3\u4e48\u603b\u662fi’\u5728\u4e0a\u9762\u66f4\u597d\u3002\u3002\u3002\u540c\u7406\u5982\u679cA+B=A’+B’\u3002\u3002\u90a3\u4e48\uff22\u5927\u7684\u5728\u4e0a\u9762\u597d\u3002\u3002\u3002\u76f4\u63a5\u6392\u5e8f\u5c31OK\u4e86\u3002\u3002#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int maxn=50000,inf=~0U>>1;int n;struct node{ int w,s; bool operator<(const node&x) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/43"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=43"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/43\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=43"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=43"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=43"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}