USACO 2008 Jan Silver

题目来自PKU。。
PKU太强大了。。有差不多200道USACO的月赛题(可以搜索之)。。。
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
官方题解。。http://ace.delos.com/JAN08
1个半小时A完阿。。病好了状态暴涨阿。。要是NOIP的时候。。(这个烧饼又开始作白日梦了。。
@@@@1@@@@
很容易看出谁强谁弱的关系是传递的。。直接传递闭包。。
那么一个人位置确定就是打败他的人+他打败的人+他自己=总人数。。
#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@@@@
暴力DP阿。。还能干WHAT?
D[i]为i开始时那啥啥为0时能跑多远。。
睡大觉:D[i]->D[i+1]..
跑K步。。再休息K分钟(劳逸结合?)。。D[i]+Sum[i..i+j]->D[i+2j]。。
注意答案是D[N+1](N+1分钟开始的时候就是N分钟结束的时候。。)
#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@@@@
这个有点意思。。
设F[i][u]是在i点。用了u次特权(就是耍赖不交费。。)。。所需费用的最小值。。
我们共产党与民一心,不搞特权:F[i][u]->F[i][u+1]。。
连接阿。。:设j与i相连。。F[j][u]=max(Cost[i][j],F[i][u]),F[j][u+1]=F[i][u];
用SPFA更新来更新去就OK了。。。
答案是F[N][K]。。。
#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();
}

3 thoughts on “USACO 2008 Jan Silver

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>