我看这题似乎没有将状态转移方程讲清楚的题解啊，所以我来了
入题。
看到这题，我立马想到贪心。
对题意，我的错误的理解为：对于任意一个能量菜单上的能量值都可以在任意时间充电。这样，就可以直接排序选前 k k k个最小值进行充电。
然后，我看到了此题的颜色：普及+/提高
这题不简单！
于是，我就看到了讨论中的：
贪心60分求助
算法疑问
是题目问题还是我的问题
哦原来是 按一定顺序 给出了 N N N 个单位的能量值，使用也得 按一定顺序 。也就是说，用了第 i i i个后，第 i i i个之前的就不能再用了。
好了，排序不能用了，决策题只能考虑动态规划了。
于是设 f [ i ] [ j ] f[i][j] f[i][j]表示在第 i i i个之前使用了 j j j种能量值时最少用的天数。
比如说对于样例， f [ 3 ] [ 2 ] f[3][2] f[3][2]表示第三个能量值之前的三种能量值1,119,119中要选择两个能量值并充电给小Q。
考虑i和j之间关系。
若 i==j
若 i = = j i==j i==j，也就是说前 i i i个一定要全部选，那么第 i i i项也一定要选。那么就考虑选择第 i i i个：
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + ( t [ i − 1 ] [ j − 1 ] + n u m [ i ] > 119 ) ? 1 : 0 f[i][j]=f[i-1][j-1]+(t[i-1][j-1]+num[i]>119)? 1:0 f[i][j]=f[i−1][j−1]+(t[i−1][j−1]+num[i]>119)?1:0
看起来那么长，其实就是将一个if嵌在其中。
首先， f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i−1][j−1]指前一个选择了 j − 1 j-1 j−1项的状态，到此状态是刚好选择 j j j项。
而后面的一个三元运算，则指是否需要重新的一天来充电——用题目的话来说就是充电量超过了119，则要用另一天来充电。否则小Q就要原地爆炸
注：t数组保存着在第i,j状态时那一天已经用了多少能量；
若 i>j
再考虑 i > j i>j i>j。这表示在前 i i i种能量值中只用选择j个，而并不用全部选完。这就又分两种情况：
（1）不选第i种能量。
（2）选第i种能量。
对于（2），在i==j时我们已经讨论过了，那么只需要Ctrl-C+V就好了。
对于（1），直接 f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i−1][j]就得了，没啥要考虑的。
只要对比（1）和（2）的大小就OK了。
依照上面的思路，我们可以写出这个简单的代码。
（不要着急复制粘贴AC这道题啊，因为下面的代码只有30分）
#include<bits/stdc++.h>
using namespace std;
int num[3001],f[3001][3001],t[3001][3001];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>num[i];
for(int i=1;i<=n;i++) f[i][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
if(i==j)
{ //选取当前能量
f[i][j]=f[i-1][j-1];
t[i][j]=t[i-1][j-1]+num[i];
if(t[i][j]>119)
{
t[i][j]=num[i];
f[i][j]++;
}
}
else
{
if(f[i-1][j]<f[i-1][j-1]+(t[i-1][j-1]+num[i]>119)? 1:0)
{ //不选取当前能量
f[i][j]=f[i-1][j];
t[i][j]=t[i-1][j];
}
else
{ //选取当前能量
f[i][j]=f[i-1][j-1];
t[i][j]=t[i-1][j-1]+num[i];
if(t[i][j]>119)
{
t[i][j]=num[i];
f[i][j]++;
}
}
}
}
cout<<f[n][k]+(t[n][k]!=0)? 1:0; //此处要将最后一天算上，f[n][k]并没有将当时所用的天数包含在内，即在使用的第一天f[i][j]还是0
return 0;
}
好，为什么30分呢？等等， i > j i>j i>j的情况没考虑完整！若选择和不选择的天数相同呢？
先停一下，看看 f [ i ] [ j ] f[i][j] f[i][j]的含义。它表示在第 i i i个之前使用了 j j j种能量值时最少用的天数（的向下取整）。对啊！这使当前这一天的使用的能量没有发挥作用啊！
还是举个粒子吧。
现在已经使用了这样的能量组合：
118 1 50
到第三天时，用了1天并还剩下50的能量。剩下的50能量便是主要要对比的对象了。
那么，天数相同时，最后一天所用的能量肯定越少要好啊！所以，在天数相同的情况下，就选择最后一天使用能量较少得那一种方案。
于是代码变成了这样：
#include<bits/stdc++.h>
using namespace std;
int num[3001],f[3001][3001],t[3001][3001];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>num[i];
for(int i=1;i<=n;i++) f[i][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
if(i==j)
{
f[i][j]=f[i-1][j-1];
t[i][j]=t[i-1][j-1]+num[i];
if(t[i][j]>119)
{
t[i][j]=num[i];
f[i][j]++;
}
}
else
{
if(f[i-1][j]<f[i-1][j-1]+(t[i-1][j-1]+num[i]>119)? 1:0)
{
f[i][j]=f[i-1][j];
t[i][j]=t[i-1][j];
}
else if(f[i-1][j]==f[i-1][j-1]+(t[i-1][j-1]+num[i]>119)? 1:0) //此处考虑相同的情况
{
if(t[i-1][j]<=((t[i-1][j-1]+num[i])>119? num[i]:t[i-1][j-1]+num[i])) //这里注意三元运算的优先级
{
f[i][j]=f[i-1][j];
t[i][j]=t[i-1][j];
}
else
{
f[i][j]=f[i-1][j-1];
t[i][j]=t[i-1][j-1]+num[i];
if(t[i][j]>119)
{
t[i][j]=num[i];
f[i][j]++;
}
}
}
else
{
f[i][j]=f[i-1][j-1];
t[i][j]=t[i-1][j-1]+num[i];
if(t[i][j]>119)
{
t[i][j]=num[i];
f[i][j]++;
}
}
}
}
cout<<f[n][k]+(t[n][k]!=0)? 1:0;
return 0;
}
完结。
等等？为什么没有“You can’t do it.”都可以的？
哈哈哈，这说明了一些显而易见的事实。
既然想到了那么就说一说怎么判断吧。如何凑出不可能充k种电的情况呢？
只有一种情况，就是没有足够的方式充电。
那么输入就可以改成这样：
int cnt=0;
for(int i=1;i<=n;i++)
cin>>num[i],cnt+=(num[i]<=119);
if(cnt<k) puts("You can't do it."); //没有足够的种类去充电
正式完结。
有不懂得问题，问我哈
有错误请指出，方便我改进自身qwq