我看这题似乎没有将状态转移方程讲清楚的题解啊，所以我来了
入题。
看到这题，我立马想到贪心。
对题意，我的错误的理解为：对于任意一个能量菜单上的能量值都可以在任意时间充电。这样，就可以直接排序选前个最小值进行充电。
然后，我看到了此题的颜色：普及+/提高
这题不简单！
于是，我就看到了讨论中的：
贪心60分求助
算法疑问
是题目问题还是我的问题
哦原来是 按一定顺序 给出了 个单位的能量值，使用也得 按一定顺序 。也就是说，用了第 个后，第 个之前的就不能再用了。
好了，排序不能用了，决策题只能考虑动态规划了。
于是设 表示在第 个之前使用了 种能量值时最少用的天数。
比如说对于样例， 表示第三个能量值之前的三种能量值1,119,119中要选择两个能量值并充电给小Q。
考虑 和 之间关系。
若 i==j
若 ，也就是说前 个一定要全部选，那么第 项也一定要选。那么就考虑选择第 个：
看起来那么长，其实就是将一个if嵌在其中。
首先， 指前一个选择了 项的状态，到此状态是刚好选择 项。
而后面的一个三元运算，则指是否需要重新的一天来充电——用题目的话来说就是充电量超过了119，则要用另一天来充电。否则小Q就要原地爆炸
注： 数组保存着在第 , 状态时那一天已经用了多少能量；
若 i>j
再考虑 。这表示在前 种能量值中只用选择 个，而并不用全部选完。这就又分两种情况：
（1）不选第 种能量。
（2）选第 种能量。
对于（2），在 时我们已经讨论过了，那么只需要Ctrl-C+V就好了。
对于（1），直接 就得了，没啥要考虑的。
只要对比（1）和（2）的大小就OK了。
依照上面的思路，我们可以写出这个简单的代码。
（不要着急复制粘贴AC这道题啊，因为下面的代码只有30分）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #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;
return 0;
}
|
好，为什么30分呢？等等， 的情况没考虑完整！若选择和不选择的天数相同呢？
先停一下，看看 的含义。它表示在第 个之前使用了 种能量值时最少用的天数（的向下取整）。对啊！这使当前这一天的使用的能量没有发挥作用啊！
还是举个粒子吧。
现在已经使用了这样的能量组合：
118 1 50
到第三天时，用了1天并还剩下50的能量。剩下的50能量便是主要要对比的对象了。
那么，天数相同时，最后一天所用的能量肯定越少要好啊！所以，在天数相同的情况下，就选择最后一天使用能量较少得那一种方案。
于是代码变成了这样：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #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种电的情况呢？
只有一种情况，就是没有足够的方式充电。
那么输入就可以改成这样：
1
2
3
4
| 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