dp--一种非常神奇的算法
cf的一道C题，非常经典（弱鸡没有做出来）
http://codeforces.com/contest/711/problem/C
这是一道三维dp，题目意思是有m种颜料，给n颗树中为0的染色目的是相邻的不同的个数为k，输出最小的颜料
好难！！！！！！！！！！！！！！
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const ll maxn = 1e18+10; 5 ll a[120], b[120][120],dp[120][120][120], sum = maxn; 6 int main(){ 7 int n, m, k; 8 cin>>n>>m>>k; 9 for(int i = 1; i <= n; i++){ 10 cin>>a[i]; 11 } 12 for(int i = 1; i <= n; i++){ 13 for(int j = 1; j <= m; j++) 14 cin>>b[i][j]; 15 } 16 for(int i = 1; i <= n; i++){ 17 for(int j = 1; j <= m; j++){ 18 for(int k = 0; k <= n; k++){ //神奇 k=1; 19 dp[i][j][k] = maxn; 20 } 21 } 22 } 23 // dp[0][0][0] = 0; 24 for(int i = 1; i <= n; i++){ 25 for(int j = 1; j <= i; j++){ 26 if(a[i]){ 27 dp[i][a[i]][j] = dp[i-1][a[i]][j]; 28 for(int k = 1; k <= m; k++){ 29 if(a[i]!=k) 30 dp[i][a[i]][j] = min(dp[i][a[i]][j], dp[i-1][k][j-1]); 31 } 32 } 33 else{ 34 for(int x = 1; x <= m; x++){ 35 for(int y = 1; y <= m; y++){ 36 if(x == y) dp[i][y][j] = min(dp[i][y][j],dp[i-1][x][j]+b[i][y]); 37 else dp[i][y][j] = min(dp[i][y][j], dp[i-1][x][j-1]+b[i][y]); 38 } 39 } 40 } 41 } 42 } 43 for(int i = 1; i <= m; i++){ 44 // cout<<dp[n][i][k]<<endl; 45 sum = min(sum,dp[n][i][k]); 46 } 47 cout<<(sum >= maxn ? -1: sum)<<endl; 48 }
hdu 2577
http://acm.split.hdu.edu.cn/showproblem.php?pid=2577
非常经典的dp，，shift 和 caps lock 输入大小写
神奇！！！！！！！！！！！！！！
1 #include <iostream> 2 #include <string> 3 using namespace std; 4 int dp[120][3]; 5 int main(){ 6 int n, num; 7 string str; 8 cin>>n; 9 while(n--){ 10 num = 0; 11 cin>>str; 12 int len = str.length(); 13 dp[0][0] = 0; 14 dp[0][1] = 1; 15 for(int i = 0; i < len; i++){ 16 if(islower(str[i])){ 17 dp[i+1][0]=min(dp[i][0]+1, dp[i][1]+2); 18 dp[i+1][1]=min(dp[i][0]+2, dp[i][1]+2); 19 } 20 else{ 21 dp[i+1][0]=min(dp[i][0]+2, dp[i][1]+2); 22 dp[i+1][1]=min(dp[i][0]+2, dp[i][1]+1); 23 } 24 } 25 cout<<min(dp[len][1]+1, dp[len][0])<<endl; 26 } 27 }
dp的神奇在于每个数组的下标都表示某种特殊的状态，用来描述事物而不是单纯的数组，重点是找到前后的关系即动态转移方程
dp的特点是反复操作每次操作的步骤和结果都是固定的。。。。
只有不断学习才能进步！