朴素做法暴力DP，O(nk)过不去。。。
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #define N1 2005
6 #define ll long long
7 using namespace std;
8
9 int n,p;
10 int l[N1],r[N1],a[N1];
11 ll f[N1][N1];
12 ll linf=0x3f3f3f3f3f3fll;
13
14 int main()
15 {
16 freopen("a.txt","r",stdin);
17 scanf("%d%d",&n,&p);
18 for(int i=1;i<=n;i++) scanf("%d%d%d",&l[i],&r[i],&a[i]);
19 for(int i=0;i<=n;i++) for(int k=0;k<=p;k++) f[i][k]=linf;
20 f[0][p]=0; l[n+1]=r[n]+1;
21 for(int i=1;i<=n;i++)
22 {
23 for(int k=0;k<p;k++)
24 {
25 if(a[i]%p<=k)
26 {
27 if(a[i]/p<=r[i]-l[i])
28 {
29 f[i][k-a[i]%p]=f[i-1][k]+a[i]/p;
30 if(a[i]/p+1<=l[i+1]-l[i]) f[i][p]=min(f[i][p],f[i-1][k]+a[i]/p+1);
31 }
32 }
33 if(a[i]%p>k)
34 {
35 if(a[i]/p+1<=r[i]-l[i])
36 {
37 f[i][k+p-a[i]%p]=f[i-1][k]+a[i]/p+1;
38 if(a[i]/p+2<=l[i+1]-l[i]) f[i][p]=min(f[i][p],f[i-1][k]+a[i]/p+2);
39 }
40 }
41 }
42 if(a[i]%p)
43 {
44 if(a[i]/p<=r[i]-l[i])
45 {
46 f[i][p-a[i]%p]=f[i-1][p]+a[i]/p;
47 if(a[i]/p+1<=l[i+1]-l[i]) f[i][p]=min(f[i][p],f[i-1][p]+a[i]/p+1);
48 }
49 }else{
50 if(a[i]/p-1<=r[i]-l[i])
51 {
52 f[i][0]=f[i-1][p]+a[i]/p-1;
53 if(a[i]/p<=l[i+1]-l[i]) f[i][p]=min(f[i][p],f[i-1][p]+a[i]/p);
54 }
55 }
56
57 }
58 ll ans=linf;
59 for(int k=0;k<=p;k++) ans=min(ans,f[n][k]*p+p-k);
60 if(ans==linf) puts("-1"); else printf("%lld\n",ans);
61 return 0;
62 }
先考虑贪心这个过程
对于从i开始连续的几波，如果我们只进行不浪费子弹的换弹，我们都可以到达那些波，同时记录到达这些波换的弹夹数g[i][j]，处理出这两个数组的时间是O(n)，总时间O(n^2)
然后进行DP，f[i]记录答案，表示处理完前i-1波消耗的子弹数，那么f[i]可以由所有贪心到达i-1的点j转移过来，f[i]=min(f[j]+g[j][i-1]*p)，注意如果i和i-1之间有间隙时间，是可以转移的
总结：贪心可以处理时间充裕的情况，而DP则用来求解必须满弹开始的情况
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #define N1 2005
6 #define ll long long
7 using namespace std;
8
9 int n,p;
10 int l[N1],r[N1],a[N1];
11 ll f[N1],g[N1][N1],Rem[N1];
12 bool ok[N1][N1];
13 ll linf=0x3f3f3f3f3f3fll;
14 int divup(int x,int y)
15 {
16 if(x%y) return x/y+1;
17 else return x/y;
18 }
19
20 int main()
21 {
22 // freopen("a.txt","r",stdin);
23 scanf("%d%d",&n,&p);
24 for(int i=1;i<=n;i++) scanf("%d%d%d",&l[i],&r[i],&a[i]);
25 int rem,cnt,tim,num;
26 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=linf;
27 for(int i=2;i<=n;i++) f[i]=linf;
28 for(int i=1;i<=n;i++)
29 {
30 //greedy
31 num=divup(a[i],p);
32 if(num-1<=r[i]-l[i]) //start with full
33 {
34 g[i][i]=cnt=num, rem=num*p-a[i];
35 Rem[i]=rem;
36 if(num<=r[i]-l[i]) //supply if empty
37 {
38 ok[i][i]=1;
39 if(rem==0) rem=p, cnt++;
40 }
41 for(int j=i+1;j<=n;j++) //never throw away remaining bullets
42 {
43 if(rem>a[j]){
44 rem-=a[j], g[i][j]=cnt;
45 }else{
46 num=divup(a[j]-rem,p); //never reload between consecutive waves
47 if(num<=r[j]-l[j]) g[i][j]=cnt=cnt+num, rem=num*p+rem-a[j];
48 else{
49 break;
50 }
51 }
52 Rem[i]=rem;
53 if(num+1<=r[j]-l[j])
54 {
55 if(rem==0) rem=p, cnt++;//supply if empty
56 ok[i][j]=1;
57 }
58 }
59 }else{
60 puts("-1"); return 0;
61 }
62 }
63 f[1]=0;
64 for(int i=2;i<=n;i++)
65 {
66 //DP
67 for(int j=1;j<i;j++)
68 {
69 if(g[j][i-1]!=linf && (ok[j][i-1] || r[i-1]<l[i] ) )
70 f[i]=min(f[i],f[j]+g[j][i-1]*p);
71 }
72 }
73 ll ans=linf;
74 for(int i=1;i<=n;i++)
75 if(g[i][n]<linf/2) ans=min(ans,f[i]+g[i][n]*p-Rem[i]);
76 if(ans>=linf/2) puts("-1"); else printf("%lld\n",ans);
77 return 0;
78 }
79
