题解 P1687 【机器人小Q】

LeavingZzz · 2020-08-09 10:43:58 · 题解

\mathsf{Solution\space For\space P1687}

Update On 2022/11/17 : 修了一处 typo 与若干个不合理的公式。

非常好的一道分类讨论类的 dp。

\mathsf{Analysis}

首先我们设计状态
令 f[i][j] 为前 i 个能量单位中选取 j 个能量单位所用的最小天数。

但是很快你就会发现这样设计状态是有bug的，因为每天充电的上限是 119，状态设计成这样无法体现这一限制，于是考虑扩展一下。

令 f[i][j][1] 表示在前 i 个能量单位中选取 j 个能量单位用的最小天数，令 f[i][j][0] 表示当天数最小时最后一天的充电时长最短为多久。
（即，以天数为第一关键字，以最后一天充电的时长为第二关键字选取最优解）

然后研究状态转移方程

对于第 i 个能量单位我们考虑 选/不选 两种情况

如果我们选取第 i 个能量单位

此时当前状态 f[i][j] 将由 f[i-1][j-1] 转移而来，根据我们对状态关键字的描述，我们应该考虑以下两种情况

f[i-1][j-1][0]+w[i]>119

这时候我们应该增加新的一天来使用第 i 个能量单位
因此比较 f[i-1][j-1][1]+1 与 f[i][j][1] 的大小关系。

若 f[i-1][j-1][1]+1<f[i][j][1]
那么此时选取第 i 个能量单位的决策一定优于 f[i][j] 的决策

若 f[i-1][j-1][1]+1=f[i][j][1]，那么这时候比较第二关键字

f[i-1][j-1][0]+w[i]\le119

这时候考虑将第 i 个能量单位追加到最后一天内，仍然按序比较两个关键字

若 f[i-1][j-1][1]<f[i][j][1]
此时选取第 i 个能量单位的决策一定优于 f[i][j] 的决策

若 f[i-1][j-1][1]=f[i][j][1]
此时比较第二关键字

如果我们不选取第 i 个能量单位

这时候直接继承前面的状态

分析完毕，还有问题请看代码QwQ

\mathsf{Code}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=3007;
int F[maxn][maxn][2];
int N,K;
int w[maxn],cnt;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&w[++cnt]);
        if(w[cnt]>119) --cnt;//大于119可以直接丢掉，怎么都用不上
    }
    //如果可用的能量单位不足K个那么无解
    if(cnt<K) {printf("You can't do it.");return 0;}
    memset(F,0x3f,sizeof(F));//初始化
    for(int i=0;i<=cnt;i++)//无论是多少个数字分成0段花费0天
        F[i][0][1]=0;
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=min(i,K);j++)
        {
            //先继承
            F[i][j][0]=F[i-1][j][0];
            F[i][j][1]=F[i-1][j][1];
            //考虑选取第i个
            //是否需要新增一天
            if(F[i-1][j-1][0]+w[i]>119)
            {
                if(F[i-1][j-1][1]+1<F[i][j][1])
                    F[i][j][1]=F[i-1][j-1][1]+1,F[i][j][0]=w[i];
                else if(F[i-1][j-1][1]+1==F[i][j][1])
                    F[i][j][0]=min(w[i],F[i][j][0]);
            }
            //直接追加到最后一天
            else
            {
                if(F[i-1][j-1][1]<F[i][j][1])
                    F[i][j][1]=F[i-1][j-1][1],F[i][j][0]=F[i-1][j-1][0]+w[i];
                else if(F[i-1][j-1][1]==F[i][j][1])
                    F[i][j][0]=min(F[i-1][j-1][0]+w[i],F[i][j][0]);
            }
        }
    /*for(int i=1;i<=cnt;i++)
        for(int j=1;j<=min(i,K);j++)
            printf("F[%d][%d]={%d,%d}\n",i,j,F[i][j][0],F[i][j][1]);*/
    printf("%d",F[cnt][K][1]);//答案即为F[cnt][K][1]
    return 0;
}

谢谢管理大大审核^_^