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+;
typedef long long ll;
inline ll read(){
char c=getchar();ll x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';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=,ans=;
int main(){
//freopen("flower.in","r",stdin);
//freopen("flower.out","w",stdout);
n=read();
for(int i=;i<=n;i++){
a[i].t=*read();a[i].w=read();
sum+=a[i].w;
}
sort(a+,a++n);
for(int i=;i<=n;i++){sum-=a[i].w;ans+=sum*a[i].t;}
printf("%lld\n",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递增
//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+;
typedef long long ll;
const ll INF=1e18;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,k,w[N];
ll f[N];
void dp(){
f[]=;
for(int i=;i<=n;i++) f[i]=-INF;
for(int i=;i<=n;i++){
int tmp=f[];
f[]=max(f[],f[k]);
for(int j=k;j>=;j--){
f[]=max(f[],f[j-]);
f[j]=f[j-]+w[i];//printf("%d %d %d\n",i,j,f[j]);
}
f[]=tmp+w[i];//printf("%d 0 %d\n",i,f[0]);
//printf("%d 1 %d\n",i,f[1]);
}
}
int main(){
freopen("mowlawn.in","r",stdin);
freopen("mowlawn.out","w",stdout);
n=read();k=read();
for(int i=;i<=n;i++) w[i]=read();
dp();
ll ans=-INF;
for(int i=;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+;
typedef long long ll;
const ll INF=1e18;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,k,w[N];
ll f[N],sum=;
int q[N],head=,tail=;
void dp(){
q[++tail]=;
for(int i=;i<=n;i++){
while(i-q[head]->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\n",i,f[i]);
}
}
int main(){
//freopen("mowlawn.in","r",stdin);
//freopen("mowlawn.out","w",stdout);
n=read();k=read();
for(int i=;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=,M=1e4,INF=1e9;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int T,n,m,mm,u,v,w;
struct edge{
int v,ne,w;
}e[M];
int cnt=,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,,sizeof(inq));
memset(num,,sizeof(num));
for(int i=;i<=n;i++) d[i]=INF;
q.push();inq[]=;d[]=;
while(!q.empty()){
int u=q.front();q.pop();inq[u]=;
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]=;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=;
memset(h,,sizeof(h));
for(int i=;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);ins(v,u,w);}
for(int i=;i<=mm;i++){u=read();v=read();w=read();ins(u,v,-w);}
if(!spfa()) printf("YES\n");
else printf("NO\n");
}
}