自动搬运

查看原文

来自洛谷，原作者为

	LeavingZzz 生当如夏花绚烂，死当如秋叶静美

搬运于2025-08-24 21:27:56，当前版本为作者最后更新于2020-08-09 10:43:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\mathsf{Solution\space For\space P1687}$

$\mathsf{By\space LeavingZ}$
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][j][1]=f[i-1][j-1][1]+1,f[i][j][0]=w[i]$

若 $f[i-1][j-1][1]+1=f[i][j][1]$，那么这时候比较第二关键字
$f[i][j][0]=\min(w[i],f[i][j][0])$

$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][j][1]=f[i-1][j-1][1],f[i][j][0]=f[i-1][j-1][0]+w[i]$

若 $f[i-1][j-1][1]=f[i][j][1]$
此时比较第二关键字
$f[i][j][0]=\min(f[i][j][0],f[i-1][j-1][0]+w[i])$

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

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

$f[i][j][0]=f[i-1][j][0],f[i][j][1]=f[i-1][j][1]$

分析完毕，还有问题请看代码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;
}

$\huge\mathcal{The\space End}$
谢谢管理大大审核^_^