洛谷 P5017 摆渡车

题目传送门

解题思路：

个人感觉DP这东西，只可意会，不可言传
AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 long long n,m,t[501],f[501][501],ans = 0x3f3f3f3f3f,mi;
 9 
10 int main() {
11     scanf("%lld%lld",&n,&m);
12     for(int i = 1;i <= n; i++) 
13         scanf("%lld",&t[i]),mi = mi < t[i] ? mi : t[i];    
14     for(int i = 1;i <= n; i++) t[i] -= mi;
15     sort(t+1,t+n+1);
16     memset(f,0x3f,sizeof(f));
17     for(int i = 0;i < 2 * m; i++) f[1][i] = i;
18     for(int i = 1;i < n; i++)
19         for(int j = 0;j < 2 * m; j++) {
20             if(f[i][j] < 0x3f3f3f3f3f3f3f3f) {
21                 if(t[i] + j >= t[i+1])
22                     f[i+1][t[i]+j-t[i+1]] = min(f[i+1][t[i]+j-t[i+1]],f[i][j]+j+t[i]-t[i+1]);
23                 for(int k = t[i] + j + m >= t[i+1] ? 0 : t[i+1] - t[i] - j - m;t[i] + j + m + k - t[i+1] < 2 * m; k++)
24                     if(t[i] + j + k + m >= t[i+1])
25                         f[i+1][t[i]+j+k+m-t[i+1]] = min(f[i+1][t[i]+j+k+m-t[i+1]],f[i][j]+t[i]+j+m+k-t[i+1]);
26                 if(t[i] + j + m < t[i+1])
27                     for(int k = 0;k < m * 2; k++)
28                         f[i+1][k] = min(f[i+1][k],f[i][j] + k); 
29             }
30         }
31     for(int i = 0;i < m * 2; i++)
32         ans = min(ans,f[n][i]);
33     printf("%lld",ans);
34     return 0;
35 }
//NOIP2018普及 T3