{"id":41,"date":"2009-11-26T14:29:00","date_gmt":"2009-11-26T06:29:00","guid":{"rendered":"http:\/\/localhost\/?p=41"},"modified":"2009-11-26T14:29:00","modified_gmt":"2009-11-26T06:29:00","slug":"usaco_2008_jan_silver","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=41","title":{"rendered":"USACO 2008 Jan Silver"},"content":{"rendered":"

\u9898\u76ee\u6765\u81eaPKU\u3002\u3002
PKU\u592a\u5f3a\u5927\u4e86\u3002\u3002\u6709\u5dee\u4e0d\u591a200\u9053USACO\u7684\u6708\u8d5b\u9898\uff08\u53ef\u4ee5\u641c\u7d22\u4e4b\uff09\u3002\u3002\u3002
http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3660 Cow Contest
http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3661 Running
http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3662 Telephone Lines
\u5b98\u65b9\u9898\u89e3\u3002\u3002http:\/\/ace.delos.com\/JAN08
1\u4e2a\u534a\u5c0f\u65f6A\u5b8c\u963f\u3002\u3002\u75c5\u597d\u4e86\u72b6\u6001\u66b4\u6da8\u963f\u3002\u3002\u8981\u662fNOIP\u7684\u65f6\u5019\u3002\u3002\uff08\u8fd9\u4e2a\u70e7\u997c\u53c8\u5f00\u59cb\u4f5c\u767d\u65e5\u68a6\u4e86\u3002\u3002
@@@@1@@@@
\u5f88\u5bb9\u6613\u770b\u51fa\u8c01\u5f3a\u8c01\u5f31\u7684\u5173\u7cfb\u662f\u4f20\u9012\u7684\u3002\u3002\u76f4\u63a5\u4f20\u9012\u95ed\u5305\u3002\u3002
\u90a3\u4e48\u4e00\u4e2a\u4eba\u4f4d\u7f6e\u786e\u5b9a\u5c31\u662f\u6253\u8d25\u4ed6\u7684\u4eba+\u4ed6\u6253\u8d25\u7684\u4eba+\u4ed6\u81ea\u5df1\uff1d\u603b\u4eba\u6570\u3002\u3002
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100;
int n,m;
bool d[maxn][maxn]={0};
int main()
{
cin>>n>>m;int s,t;
while(m–)
{
cin>>s>>t;s–;t–;
d[s][t]=true;
}
REP(k,n) REP(i,n) REP(j,n) d[i][j]=d[i][j] or (d[i][k] and d[k][j]);
int ans=0;
REP(i,n)
{
int a=0,b=0;
REP(j,n) if(d[j][i]) a++;
REP(j,n) if(d[i][j]) b++;
if(a+b==n-1) ans++;
}
cout<<ans<<endl;
}@@@@2@@@@
\u66b4\u529bDP\u963f\u3002\u3002\u8fd8\u80fd\u5e72WHAT\uff1f
D[i]\u4e3ai\u5f00\u59cb\u65f6\u90a3\u5565\u5565\u4e3a0\u65f6\u80fd\u8dd1\u591a\u8fdc\u3002\u3002
\u7761\u5927\u89c9:D[i]->D[i+1]..
\u8dd1K\u6b65\u3002\u3002\u518d\u4f11\u606fK\u5206\u949f\uff08\u52b3\u9038\u7ed3\u5408\uff1f\uff09\u3002\u3002D[i]+Sum[i..i+j]->D[i+2j]\u3002\u3002
\u6ce8\u610f\u7b54\u6848\u662fD[N+1]\uff08N+1\u5206\u949f\u5f00\u59cb\u7684\u65f6\u5019\u5c31\u662fN\u5206\u949f\u7ed3\u675f\u7684\u65f6\u5019\u3002\u3002\uff09
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=10000,maxm=500+10,inf=~0U>>1;
int n,m;
int D[maxn],S[maxn];
void init()
{
cin>>n>>m;
REP(i,n) cin>>D[i];
REP(i,n) S[i]=0;
}
inline void Renew(int&x,int c)
{
x=max(x,c);
}
void solve()
{
S[0]=0;
REP(i,n)
{
int cost=S[i];
Renew(S[i+1],cost);
int pos=i,sum=S[i];
for(int j=0;j<m&&pos<n;j++)
{
pos+=2;
sum+=D[i+j];
Renew(S[pos],sum);
}
}
cout<<S[n]<<endl;
}
int main()
{
init();
solve();
}@@@@3@@@@
\u8fd9\u4e2a\u6709\u70b9\u610f\u601d\u3002\u3002
\u8bbeF[i][u]\u662f\u5728i\u70b9\u3002\u7528\u4e86u\u6b21\u7279\u6743\uff08\u5c31\u662f\u800d\u8d56\u4e0d\u4ea4\u8d39\u3002\u3002\uff09\u3002\u3002\u6240\u9700\u8d39\u7528\u7684\u6700\u5c0f\u503c\u3002\u3002
\u6211\u4eec\u5171\u4ea7\u515a\u4e0e\u6c11\u4e00\u5fc3\uff0c\u4e0d\u641e\u7279\u6743:F[i][u]->F[i][u+1]\u3002\u3002
\u8fde\u63a5\u963f\u3002\u3002:\u8bbej\u4e0ei\u76f8\u8fde\u3002\u3002F[j][u]=max(Cost[i][j],F[i][u]),F[j][u+1]=F[i][u];
\u7528SPFA\u66f4\u65b0\u6765\u66f4\u65b0\u53bb\u5c31OK\u4e86\u3002\u3002\u3002
\u7b54\u6848\u662fF[N][K]\u3002\u3002\u3002
#include<iostream>
#include<cstdio>
#include<queue>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=1000,inf=~0U>>1;
struct edge
{
int t,c;
edge*next;
edge(int t,int c,edge*n):t(t),c(c),next(n){}
}*E[maxn];
void add(int s,int t,int c)
{
E[s]=new edge(t,c,E[s]);
E[t]=new edge(s,c,E[t]);
}
int N,P,K;
void init()
{
cin>>N>>P>>K;
while(P–)
{
int s,t,c;scanf("%d %d %d",&s,&t,&c);s–;t–;
add(s,t,c);
}
}
struct node
{
int pos,cost;
node(int p,int c):pos(p),cost(c){}
};
bool inQ[maxn][maxn]={0};
int cost[maxn][maxn];
queue<node> Q;
inline void Renew(int p,int u,int c)
{
if(u>K) return;
if(cost[p][u]>c)
{
cost[p][u]=c;
if(!inQ[p][u])
Q.push(node(p,u)),inQ[p][u]=true;
}
}
void solve()
{
REP(i,N) REP(j,K+1) cost[i][j]=inf;
Q.push(node(0,0));cost[0][0]=0;inQ[0][0]=true;
int p,u;
while(Q.size())
{
node c=Q.front();Q.pop();inQ[p=c.pos][u=c.cost]=false;
int get=cost[p][u];
Renew(p,u+1,get);
for(edge*i=E[p];i;i=i->next)
{
Renew(i->t,u,max(get,i->c));
Renew(i->t,u+1,get);
}
}
if(cost[N-1][K]==inf) cout<<-1<<endl;
else cout<<cost[N-1][K]<<endl;
}
int main()
{
init();
solve();
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u9898\u76ee\u6765\u81eaPKU\u3002\u3002PKU\u592a\u5f3a\u5927\u4e86\u3002\u3002\u6709\u5dee\u4e0d\u591a200\u9053USACO\u7684\u6708\u8d5b\u9898\uff08\u53ef\u4ee5\u641c\u7d22\u4e4b\uff09\u3002\u3002\u3002http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3660 Cow Contesthttp:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3661 Runninghttp:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=3662 Telephone Lines\u5b98\u65b9\u9898\u89e3\u3002\u3002http:\/\/ace.delos.com\/JAN081\u4e2a\u534a\u5c0f\u65f6A\u5b8c\u963f\u3002\u3002\u75c5\u597d\u4e86\u72b6\u6001\u66b4\u6da8\u963f\u3002\u3002\u8981\u662fNOIP\u7684\u65f6\u5019\u3002\u3002\uff08\u8fd9\u4e2a\u70e7\u997c\u53c8\u5f00\u59cb\u4f5c\u767d\u65e5\u68a6\u4e86\u3002\u3002@@@@1@@@@\u5f88\u5bb9\u6613\u770b\u51fa\u8c01\u5f3a\u8c01\u5f31\u7684\u5173\u7cfb\u662f\u4f20\u9012\u7684\u3002\u3002\u76f4\u63a5\u4f20\u9012\u95ed\u5305\u3002\u3002\u90a3\u4e48\u4e00\u4e2a\u4eba\u4f4d\u7f6e\u786e\u5b9a\u5c31\u662f\u6253\u8d25\u4ed6\u7684\u4eba+\u4ed6\u6253\u8d25\u7684\u4eba+\u4ed6\u81ea\u5df1\uff1d\u603b\u4eba\u6570\u3002\u3002#include<iostream>#define REP(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=100;int n,m;bool d[maxn][maxn]={0};int main(){ cin>>n>>m;int s,t; while(m–) { cin>>s>>t;s–;t–; d[s][t]=true; } REP(k,n) REP(i,n) REP(j,n) d[i][j]=d[i][j] or (d[i][k] and d[k][j]); int ans=0; REP(i,n) { int a=0,b=0; REP(j,n) if(d[j][i]) a++; REP(j,n) if(d[i][j]) b++; if(a+b==n-1) ans++; } cout<<ans<<endl;}@@@@2@@@@\u66b4\u529bDP\u963f\u3002\u3002\u8fd8\u80fd\u5e72WHAT\uff1fD[i]\u4e3ai\u5f00\u59cb\u65f6\u90a3\u5565\u5565\u4e3a0\u65f6\u80fd\u8dd1\u591a\u8fdc\u3002\u3002\u7761\u5927\u89c9:D[i]->D[i+1]..\u8dd1K\u6b65\u3002\u3002\u518d\u4f11\u606fK\u5206\u949f\uff08\u52b3\u9038\u7ed3\u5408\uff1f\uff09\u3002\u3002D[i]+Sum[i..i+j]->D[i+2j]\u3002\u3002\u6ce8\u610f\u7b54\u6848\u662fD[N+1]\uff08N+1\u5206\u949f\u5f00\u59cb\u7684\u65f6\u5019\u5c31\u662fN\u5206\u949f\u7ed3\u675f\u7684\u65f6\u5019\u3002\u3002\uff09#include<iostream>#define REP(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000,maxm=500+10,inf=~0U>>1;int n,m;int […]<\/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\/41"}],"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=41"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/41\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=41"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=41"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=41"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}