题解 P5798 【[SEERC2019]Level Up】

· · 题解

简单 dp。

考虑定义 dp 数组，有关的只有当前任务，当前一级经验和二级经验。所以定义 dp_{i,j,k} 为：当前选到了第 i 个任务，一级经验和二级经验分别为 j,k。转移是非常明显的，只需要从没做这个任务的状态转移到下一个状态即可。

重要的是做任务的顺序不同，我们的答案也不同。因为一级溢出的经验会给二级，所以我们理性猜测一级能够得到的经验更多的任务放在后面。也就是把读入的任务以 x 为关键字排序。

问题解决了！

注意卡空间要开滚动数组。不要开大可能会 T。一定要开 O2，太慢了。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=0x3f3f3f3f3f3f3f3f;
LL now;
#define Nxt (now^1)
struct task{
    LL x,t,y,r;
    bool operator < (task another) const {return x<another.x;}
}p[505];
LL n,s1,s2,dp[2][505][505];
int main(){
    scanf("%lld %lld %lld",&n,&s1,&s2);
    for(LL i=1;i<=n;++i)    scanf("%lld %lld %lld %lld",&p[i].x,&p[i].t,&p[i].y,&p[i].r);
    sort(p+1,p+1+n);
    memset(dp,0x3f,sizeof dp);//气气气这里不要用 127，memset 太慢了
    dp[0][0][0]=0;
    for(LL i=1;i<=n;++i)
    {
        memcpy(dp[Nxt],dp[now],sizeof dp[now]);//滚动数组将当前状态放上去。
        for(LL j=0;j<=s1;++j)
        {
            for(LL k=0;k<=s2;++k)
            {
                if(dp[now][j][k]!=INF)
                {
                    if(j<s1)
                    {
                        LL level1=j+p[i].x;
                        if(level1>s1)
                        {
                            LL overflow=level1-s1+k;
                            overflow=min(overflow,s2);
                            dp[Nxt][s1][overflow]=min(dp[Nxt][s1][overflow],dp[now][j][k]+p[i].t);
                        }
                        else    dp[Nxt][level1][k]=min(dp[Nxt][level1][k],dp[now][j][k]+p[i].t);
                    }//将经验放在第一级，分情况讨论溢出到第二级和不溢出。
                    LL level2=k+p[i].y;
                    level2=min(level2,s2);
                    dp[Nxt][j][level2]=min(dp[Nxt][j][level2],dp[now][j][k]+p[i].r); //放在第二级
                }
            }
        }
        now^=1;
    }
    printf("%lld",(dp[now][s1][s2]==INF || !dp[now][s1][s2])?-1:dp[now][s1][s2]);//能达到满级吗
    return 0;
}