首页 > 代码库 > hdu--5074--dp
hdu--5074--dp
这算考虑不同条件下的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 <iostream> 2 #include <cstring> 3 #include <algorithm> 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]<=0 )17 {18 for( int j = m ; j>=1 ; j-- )19 {20 if( a[i-1]<=0 )21 {22 for( int k = m ; k>=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]<=0 )36 {37 for( int j = m ; j>=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<=m ; j++ )64 {65 cin >> score[i][j];66 }67 }68 for( int i = 1 ; i<=n ; i++ )69 {70 cin >> a[i];71 }72 solve( );73 for( int i = 1 ; i<=n ; i++ )74 {75 ans = max( dp[n][i] , ans );76 }77 cout << ans << endl;78 }79 return 0;80 }
today:
上次拍的微电影找不到了 不能给学妹看了 wtf
hdu--5074--dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。