2012-A3-0020

从 Trac 迁移的文章

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

原文章内容如下：

题意：甲依次经过N个部分，每个部分或者积累0（满5个不可再增加），或者可以和一个？？对打，对打是回合制，

每回合，甲先发动攻击，然后？？还击，每回合甲有一次机会喝药恢复P个hp（hp有上限），blablabla

求甲最多可打坏多少个？？，以及此情况下的最少喝药次数..


此题极不厚道的一点是，甲的攻击输出，最大HP，和恢复的P在一组case的最后，这样需要开一个数组存下之前的输入，不能在输入时完成运算，增加了额外的空间复杂度。

然后以f[i：0..5]，表示分别积累了i个0后，可以打掉的？？以及此状况下最少喝药次数

计算时，假设甲可以打掉？？，这样可以算出要扛？？回击伤害的次数。

然后计算需要的最少喝药次数，分P比一次伤害小或者不小讨论出贪心模拟出结果即可。
{{{
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> xx;
#define hp first
#define us second
#define inf -(1<<27)
int h[51200],d[51200],x[51200],H,D,P;
xx f[6];
void cmx(xx&a,xx b){if(a<b)a=b;}
const xx operator+(const xx& a,const xx& b){return xx(a.hp+b.hp,a.us+b.us);}
xx battle(int k,int d){
    if(H>k*d)return xx(1,0);
    if(d>=H)return xx(inf,0);
    for(int i=1,r=H,a=0;i<=k&&r>0;++i){
        if(r<=d)++a,r=min(H,r+P);
        r-=d;
        if(a<i&&P<d){r+=P;++a;}
        if(r>d*(k-i))return xx(1,-a);
    }
    return xx(inf,0);
}
int main(){
    for(int m,n;~scanf("%d ",&n);memset(x,0,m+1<<2)){
        for(m=0;n--;getchar()=='0'?++x[m],getchar():(scanf("%d%d ",h+m,d+m),m++));
        scanf("%d%d%d",&H,&D,&P);P=min(H-1,P);
        f[0]=xx(0,0);f[1]=f[2]=f[3]=f[4]=f[5]=xx(inf,0);
        for(int i=0;i<m;++i){
            for(int j=min(5,x[i]);j--;)
                for(int k=5;k--;)cmx(f[k+1],f[k]);
            cmx(f[0],f[5]+battle((h[i]-1)/D,d[i]));
        }
        printf("%d %d\n",f[0].hp,-f[0].us);
    }
}
}}}

题意：甲依次经过N个部分，每个部分或者积累0（满5个不可再增加），或者可以和一个？？对打，对打是回合制，

每回合，甲先发动攻击，然后？？还击，每回合甲有一次机会喝药恢复P个hp（hp有上限），blablabla

求甲最多可打坏多少个？？，以及此情况下的最少喝药次数..

此题极不厚道的一点是，甲的攻击输出，最大HP，和恢复的P在一组case的最后，这样需要开一个数组存下之前的输入，不能在输入时完成运算，增加了额外的空间复杂度。

然后以f[i：0..5]，表示分别积累了i个0后，可以打掉的？？以及此状况下最少喝药次数

计算时，假设甲可以打掉？？，这样可以算出要扛？？回击伤害的次数。

然后计算需要的最少喝药次数，分P比一次伤害小或者不小讨论出贪心模拟出结果即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> xx;
#define hp first
#define us second
#define inf -(1<<27)
int h[51200],d[51200],x[51200],H,D,P;
xx f[6];
void cmx(xx&a,xx b){if(a<b)a=b;}
const xx operator+(const xx& a,const xx& b){return xx(a.hp+b.hp,a.us+b.us);}
xx battle(int k,int d){
    if(H>k*d)return xx(1,0);
    if(d>=H)return xx(inf,0);
    for(int i=1,r=H,a=0;i<=k&&r>0;++i){
        if(r<=d)++a,r=min(H,r+P);
        r-=d;
        if(a<i&&P<d){r+=P;++a;}
        if(r>d*(k-i))return xx(1,-a);
    }
    return xx(inf,0);
}
int main(){
    for(int m,n;~scanf("%d ",&n);memset(x,0,m+1<<2)){
        for(m=0;n--;getchar()=='0'?++x[m],getchar():(scanf("%d%d ",h+m,d+m),m++));
        scanf("%d%d%d",&H,&D,&P);P=min(H-1,P);
        f[0]=xx(0,0);f[1]=f[2]=f[3]=f[4]=f[5]=xx(inf,0);
        for(int i=0;i<m;++i){
            for(int j=min(5,x[i]);j--;)
                for(int k=5;k--;)cmx(f[k+1],f[k]);
            cmx(f[0],f[5]+battle((h[i]-1)/D,d[i]));
        }
        printf("%d %d\n",f[0].hp,-f[0].us);
    }
}