prow2012-A3-0020

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
题意：打普通怪不耗血瓶可以积累一个buf，有了5个buf就可以打boss，打死boss要消耗血瓶，
可以积累一个胜利点。问取得最多胜利点的同时耗血瓶最少是多少。

主要就是耗血瓶的数量怎么求，一开始用二分血瓶数量+验证是否够，验证的方法太土，超时了，
改成f[1000][1000][10]的DP，还是太土，跑得快超时了。

猛马的求血瓶方法是特判算出来的，大家快去仰慕他的解题报告。。。
}}}





{{{

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
#define maxn 50100
int N,HP,D,P,h[maxn],d[maxn],f[maxn][6][2];
int use[maxn],rd,type[maxn];
int g[1010][1010][11];
int oo = 1000000000;

void update(int i,int j,int a,int b){
    if (a>f[i][j][0]){
        f[i][j][0] = a;
        f[i][j][1] = b;
    }else if (a==f[i][j][0]&&b<f[i][j][1]){
        f[i][j][0] = a;
        f[i][j][1] = b;
    }
}

int getg(int hp,int h,int d){
    if (hp<=0) return oo;
    if (h-D<=0) return 0;

    if (g[hp][h][d]!=-1) return g[hp][h][d];
    int Min = getg(min(HP,hp+P)-d,h-D,d) +1;
    if (hp-d>0)
    {
        Min = min(Min,getg(min(HP,hp-d+P),h-D,d)+1);
        Min = min(Min,getg(hp-d,h-D,d));
    }
    g[hp][h][d] = Min;
//  printf("%d %d %d: %d\n",hp,h,d,Min);
    return Min;
}

int main(){
    int i,j,k;
    while(scanf("%d",&N)!=EOF){
        for (i=1;i<=N;i++)
        {
            scanf("%d",type+i);
            if (type[i]==1){
                scanf("%d%d",h+i,d+i);
            }
        }
        scanf("%d%d%d",&HP,&D,&P);

        for (k = 1;k<=10;k++)
            for (j = 1000;j>0;j--)
                for (i=1;i<=HP;i++)
                    g[i][j][k] = -1;




        for (i=1;i<=N+2;i++){
            if (i<=N&&type[i]==1){
                use[i] = getg(HP,h[i],d[i]);
            }else use[i] = oo;
        //  printf("%d %d---\n",i,use[i]);
            for (j=0;j<=5;j++)
                f[i][j][0] = -1,f[i][j][1] = oo;
        }




        f[1][0][0] = f[1][0][1]  = 0;
        for (i=1;i<=N;i++)
            for (j=0;j<=5;j++)
            if (f[i][j][0]!=-1){
            if (type[i]==0) {
                update(i+1,min(j+1,5),f[i][j][0],f[i][j][1]);
            }else {
                update(i+1,j,f[i][j][0],f[i][j][1]);
                if (j==5&&use[i]<oo){
                    update(i+1,0,f[i][j][0]+1,f[i][j][1]+use[i]);
                }
            }
            }

        for (j=0;j<=5;j++)
            update(N+2,0,f[N+1][j][0],f[N+1][j][1]);
        printf("%d %d\n",f[N+2][0][0],f[N+2][0][1]);
    }
}


}}}

题意：打普通怪不耗血瓶可以积累一个buf，有了5个buf就可以打boss，打死boss要消耗血瓶，
可以积累一个胜利点。问取得最多胜利点的同时耗血瓶最少是多少。
主要就是耗血瓶的数量怎么求，一开始用二分血瓶数量+验证是否够，验证的方法太土，超时了，
改成f[1000][1000][10]的DP，还是太土，跑得快超时了。
猛马的求血瓶方法是特判算出来的，大家快去仰慕他的解题报告。。。

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
#define maxn 50100
int N,HP,D,P,h[maxn],d[maxn],f[maxn][6][2];
int use[maxn],rd,type[maxn];
int g[1010][1010][11];
int oo = 1000000000;
void update(int i,int j,int a,int b){
    if (a>f[i][j][0]){
        f[i][j][0] = a;
        f[i][j][1] = b;
    }else if (a==f[i][j][0]&&b<f[i][j][1]){
        f[i][j][0] = a;
        f[i][j][1] = b;
    }
}
int getg(int hp,int h,int d){
    if (hp<=0) return oo;
    if (h-D<=0) return 0;
    if (g[hp][h][d]!=-1) return g[hp][h][d];
    int Min = getg(min(HP,hp+P)-d,h-D,d) +1;
    if (hp-d>0)
    {
        Min = min(Min,getg(min(HP,hp-d+P),h-D,d)+1);
        Min = min(Min,getg(hp-d,h-D,d));
    }
    g[hp][h][d] = Min;
//  printf("%d %d %d: %d\n",hp,h,d,Min);
    return Min;
}
int main(){
    int i,j,k;
    while(scanf("%d",&N)!=EOF){
        for (i=1;i<=N;i++)
        {
            scanf("%d",type+i);
            if (type[i]==1){
                scanf("%d%d",h+i,d+i);
            }
        }
        scanf("%d%d%d",&HP,&D,&P);
        for (k = 1;k<=10;k++)
            for (j = 1000;j>0;j--)
                for (i=1;i<=HP;i++)
                    g[i][j][k] = -1;
        for (i=1;i<=N+2;i++){
            if (i<=N&&type[i]==1){
                use[i] = getg(HP,h[i],d[i]);
            }else use[i] = oo;
        //  printf("%d %d---\n",i,use[i]);
            for (j=0;j<=5;j++)
                f[i][j][0] = -1,f[i][j][1] = oo;
        }
        f[1][0][0] = f[1][0][1]  = 0;
        for (i=1;i<=N;i++)
            for (j=0;j<=5;j++)
            if (f[i][j][0]!=-1){
            if (type[i]==0) {
                update(i+1,min(j+1,5),f[i][j][0],f[i][j][1]);
            }else {
                update(i+1,j,f[i][j][0],f[i][j][1]);
                if (j==5&&use[i]<oo){
                    update(i+1,0,f[i][j][0]+1,f[i][j][1]+use[i]);
                }
            }
            }
        for (j=0;j<=5;j++)
            update(N+2,0,f[N+1][j][0],f[N+1][j][1]);
        printf("%d %d\n",f[N+2][0][0],f[N+2][0][1]);
    }
}