hdu5074dp的动态规划解法是怎样的？

本文共计571个文字，预计阅读时间需要3分钟。

这个算法考的是不同条件下的dp问题。主要是一层层递推，关键是dp状态的定义。不能想错了，dp[x,y]在第x个位置编码为y时，可以获得X个位置的值总和。因为任意一个值都是由score[...]加上这个算考得到的。

这算考虑不同条件下的dp吧一层一层递推过去主要是dp状态的定义不能想错了dp[x,y]在第x个位置编号为y的时候可以获得的前X个位置获得的价值总额因为任何一个价值都是由score[

这算考虑不同条件下的dp吧

一层一层递推过去  主要是dp状态的定义不能想错了

dp[x,y]在第x个位置编号为y的时候可以获得的前X个位置获得的价值总额

因为任何一个价值都是由 score[x,x+1]构成的 所以我们可以从i =2开始遍历 因为1的时候 答案肯定是0

然后就是对于a[x] , a[x-1] ( x>=2 ) 正负号不同情况的分析了 这里 内存循环 m 的遍历顺序是没有关系 正序 逆序无所谓

状态转移方程呢 就是

dp[x,y] = max( dp[x,y] , dp[x-1,z] + score[z][y] )其实方程不止一个 你可以看代码里不同情况的分析 主要是这种情况最难表示点

感觉 这代码 写下来特别清爽

1 #include 2 #include 3 #include 4 using namespace std; 5 6 int n , m; 7 const int size = 110; 8 int a[size]; 9 int score[size][size];10 int dp[size][size];11 12 void solve( )13 {14 for( int i = 2 ; i<=n ; i++ )15 {16 if( a[i]=1 ; j-- )19 {20 if( a[i-1]=1 ; k-- )23 {24 dp[i][j] = max( dp[i][j] , dp[i-1][k] + score[k][j] );25 }26 }27 else28 {29 dp[i][j] = max( dp[i][j] , dp[i-1][ a[i-1] ] + score[ a[i-1] ][j] );30 }31 }32 }33 else34 {35 if( a[i-1]=1 ; j-- )38 {39 dp[i][ a[i] ] = max( dp[i][ a[i] ] , dp[i-1][j] + score[j][ a[i] ] );40 }41 }42 else43 {44 dp[i][ a[i] ] = max( dp[i][ a[i] ] , dp[i-1][ a[i-1] ] + score[ a[i-1] ][ a[i] ] );45 }46 }47 }48 }49 50 int main()51 {52 cin.sync_with_stdio(false);53 int t;54 int ans;55 cin >> t;56 while( t-- )57 {58 memset( dp , 0 , sizeof(dp) );59 ans = 0;60 cin >> n >> m;61 for( int i = 1 ; i<=m ; i++ )62 {63 for( int j = 1 ; j> score[i][j];66 }67 }68 for( int i = 1 ; i> a[i];71 }72 solve( );73 for( int i = 1 ; i<=n ; i++ )74 {75 ans = max( dp[n][i] , ans );76 }77 cout < endl;78 }79 return 0;80 }View Code

today:

　　上次拍的微电影找不到了 不能给学妹看了 wtf

hdu--5074--dp