Problem 1 护花(flower.cpp/c/pas)
【题目描述】
约翰留下他的N(N<=100000)只奶牛上山采木．他离开的时候，她们像往常一样悠闲地在草场里吃草．可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚． 牛们从1到N编号．第i只牛所在的位置距离牛棚Ti(1≤Ti≤2000000)分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食Di(1≤Di≤100)朵鲜花．无论多么努力，约翰一次只能送一只牛回棚．而运送第第i只牛事实上需要2Ti分钟，因为来回都需要时间． 写一个程序来决定约翰运送奶牛的顺序，使最终被吞食的花朵数量最小．
【输入格式】
第1行输入N，之后N行每行输入两个整数Ti和Di
【输出格式】
一个整数，表示最小数量的花朵被吞食
【样例输入】
6
3 1
2 5
2 3
3 2
4 1
1 6
【样例输出】
86
【样例解释】
约翰用6，2，3，4，1，5的顺序来运送他的奶牛
POJ3262
yy各种贪心
国王游戏白做了，拿出相邻两个考虑.....
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5; typedef long long ll; inline ll read(){ char c=getchar();ll x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n; struct cow{ ll t,w; bool operator < (const cow &r)const{return t*r.w<r.t*w;} }a[N]; ll sum=0,ans=0; int main(){ //freopen("flower.in","r",stdin); //freopen("flower.out","w",stdout); n=read(); for(int i=1;i<=n;i++){ a[i].t=2*read();a[i].w=read(); sum+=a[i].w; } sort(a+1,a+1+n); for(int i=1;i<=n;i++){sum-=a[i].w;ans+=sum*a[i].t;} printf("%lld ",ans); }
Problem 2 修剪草坪(mowlawn.cpp/c/pas)
【题目描述】
在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，
新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。
然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N
(1 <= N <= 100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，
奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。
靠近的奶牛们很熟悉，因此，如果FJ安排超过K（1<=K<=N）只连续的奶牛，那么，这些奶牛就会罢工
去开派对:)。因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中
没有连续的超过K只奶牛。
【输入格式】
* 第一行：空格隔开的两个整数N和K
* 第二到N+1行：第i+1行有一个整数E_i
【输出格式】
* 第一行：一个值，表示FJ可以得到的最大的效率值。
【样例输入】
5 2
1
2
3
4
5
输入解释：
FJ有5只奶牛，他们的效率为1，2，3，4，5。他们希望选取效率总和最大的奶牛，但是
他不能选取超过2只连续的奶牛
【样例输出】
12
FJ可以选择出了第三只以外的其他奶牛，总的效率为1+2+4+5=12。
codevs4654
想了一个DP
f[i][j]表示1到i连续选了j个的最大效率
f[i][j]可以转移到f[i+1][j+1](+e[i])或者f[i+1][0]
第一维可以滚动掉，但是时间还是n^2，可以拿60分
然后就开始发现每次就是弹出f[k]插入新f[0]其他f[j]变成f[j+1]只不过加了e[i]，开始用优先队列乱搞nlogn，没挑出来
正解：
f[i]表示i不选且之前的选取都合法情况下答案损失的最小值
则f[i]=f[j]+e[i]（i-j<=k）这个显然可以用单调队列来维护
单调队列保存下标，头到尾f递增
//60 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5; typedef long long ll; const ll INF=1e18; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,k,w[N]; ll f[N]; void dp(){ f[0]=0; for(int i=1;i<=n;i++) f[i]=-INF; for(int i=1;i<=n;i++){ int tmp=f[0]; f[0]=max(f[0],f[k]); for(int j=k;j>=2;j--){ f[0]=max(f[0],f[j-1]); f[j]=f[j-1]+w[i];//printf("%d %d %d ",i,j,f[j]); } f[1]=tmp+w[i];//printf("%d 0 %d ",i,f[0]); //printf("%d 1 %d ",i,f[1]); } } int main(){ freopen("mowlawn.in","r",stdin); freopen("mowlawn.out","w",stdout); n=read();k=read(); for(int i=1;i<=n;i++) w[i]=read(); dp(); ll ans=-INF; for(int i=0;i<=k;i++) ans=max(ans,f[i]); printf("%lld",ans); }
//AC #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5; typedef long long ll; const ll INF=1e18; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,k,w[N]; ll f[N],sum=0; int q[N],head=1,tail=0; void dp(){ q[++tail]=0; for(int i=1;i<=n;i++){ while(i-q[head]-1>k) head++; f[i]=f[q[head]]+w[i]; while(f[q[tail]]>=f[i]&&head<=tail) tail--; q[++tail]=i; //printf("f %d %d ",i,f[i]); } } int main(){ //freopen("mowlawn.in","r",stdin); //freopen("mowlawn.out","w",stdout); n=read();k=read(); for(int i=1;i<=n;i++) w[i]=read(),sum+=w[i]; dp(); ll mn=INF; for(int i=n-k;i<=n;i++) mn=min(mn,f[i]); printf("%lld",sum-mn); }
Problem 3 虫洞(wormhole.cpp/c/pas)
【题目描述】
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边）连接着N （从1..N标号）块地，并有W个虫洞（有向边）。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。
【输入格式】
* Line 1: 一个整数 F, 表示农场个数。
* Line 1 of each farm: 三个整数 N, M, W。
* Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条用时T秒的小路。
* Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。
【输出格式】
* Lines 1..F: 如果John能在这个农场实现他的目标，输出"YES",否则输出"NO"。
【样例输入】
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
【样例输出】
NO
YES
POJ3259
负环
spfa
貌似题意不明确，没表达清楚是不是回到过去的必须是起点
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=505,M=1e4,INF=1e9; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int T,n,m,mm,u,v,w; struct edge{ int v,ne,w; }e[M]; int cnt=0,h[N]; inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; } int d[N],inq[N],num[N]; bool spfa(){ queue<int> q; memset(inq,0,sizeof(inq)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) d[i]=INF; q.push(1);inq[1]=1;d[1]=0; while(!q.empty()){ int u=q.front();q.pop();inq[u]=0; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v,w=e[i].w; if(d[u]<INF&&d[v]>d[u]+w){ d[v]=d[u]+w; if(!inq[v]){q.push(v);inq[v]=1;if(++num[v]>=n) return false;} } } } return true; } int main(){ freopen("wormhole.in","r",stdin); freopen("wormhole.out","w",stdout); T=read(); while(T--){ n=read();m=read();mm=read(); cnt=0; memset(h,0,sizeof(h)); for(int i=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);ins(v,u,w);} for(int i=1;i<=mm;i++){u=read();v=read();w=read();ins(u,v,-w);} if(!spfa()) printf("YES "); else printf("NO "); } }