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
     
      #include
      
       #include
       
        #include
        
         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
        
       
      
     

---

---

---

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
     
      #include
      
       #include
       
        #include
        
         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\n",i,j,f[j]);        }        f[1]=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=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
     
      #include
      
       #include
       
        #include
        
         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\n",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
     
      #include
      
       #include
       
        #include
        
         #include
         
          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
          
            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]
           
            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\n"); else printf("NO\n"); }}