首页 > 代码库 > hdu--1176---dp
hdu--1176---dp
这题的题意 一定要好好理解----touch me
当你在pos处 你下一秒能去的地方就是pos-1 pos pos+1这3个地方 而且如果你在 I 秒的时候 去了pos+1 你就不能捡到 I 秒的时候pos 和 pos-1 处掉下来的馅饼
清楚了这点 那么样例这个4 就不难得到了
这题 我想了好久 一开始 sb地想从前往后推状态...
后来 在纸上模拟下 才试了下 从后往前推
做完之后 看到hdu这题的discuss里面 有人提到了这就是 数塔 bingo啊... 都没发现 就比往常的数塔 多了一个坐标而已
这题的for进行状态转移的时候 最好在你输入时间的时候 求出这组数据的最大时间 因为时间最大可以达到100000 要是不求出来 就得从这里开始遍历 太大了。。。
这里 我们做的时候 把时间都往前进1S 这样可以不用单独地去考虑边界了 那就是用dp[ 0 ] [ 5 ] 来表示答案
当然 我们也可以还是用 dp [ 1 ][ 5 ]来表示最终答案 就是最后我们要在dp[ 1 ] [ 4 ] dp[ 1 ] [ 5 ] dp[ 1 ] [ 6 ]3者之间再进行一次max...因为我们的循环在i = 1处结束了 那么我们对于在time = 1处的选择 还没有进行处理
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int size = 100010; 6 int dp[size][15]; // 时间 坐标 7 8 int main() 9 {10 cin.sync_with_stdio(false);11 int n , dir , tim , time_max;12 while( cin >> n && n )13 {14 time_max = 0;15 memset( dp , 0 , (n+10)*11*sizeof(int) );16 for( int i = 1 ; i<=n ; i++ )17 {18 cin >> dir >> tim;19 dp[tim][dir] ++;20 time_max = max( tim , time_max );21 }22 for( int i = time_max-1 ; i>=1 ; i-- )23 {24 dp[i][0] += max( dp[i+1][0] , dp[i+1][1] );25 dp[i][10] += max( dp[i+1][10] , dp[i+1][9] );26 for( int j = 1 ; j<=9 ; j++ )27 {28 dp[i][j] += max( max( dp[i+1][j-1],dp[i+1][j] ) , max( dp[i+1][j],dp[i+1][j+1] ) );29 //cout << i << " " << j <<" "<< dp[i][j] << endl;30 }31 }32 dp[1][5] = max( max(dp[1][4],dp[1][5]),max(dp[1][5],dp[1][6]) );33 cout << dp[1][5] << endl;34 }35 return 0;36 }
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int size = 100010; 6 int dp[size][15]; // 时间 坐标 7 8 int main() 9 {10 cin.sync_with_stdio(false);11 int n , dir , tim , time_max;12 while( cin >> n && n )13 {14 time_max = 0;15 memset( dp , 0 , sizeof(dp) );16 for( int i = 1 ; i<=n ; i++ )17 {18 cin >> dir >> tim;19 dp[tim][dir] ++;20 time_max = max( tim , time_max );21 }22 for( int i = time_max-1 ; i>=0 ; i-- )23 {24 dp[i][0] += max( dp[i+1][0] , dp[i+1][1] );25 dp[i][10] += max( dp[i+1][10] , dp[i+1][9] );26 for( int j = 1 ; j<=9 ; j++ )27 {28 dp[i][j] += max( max( dp[i+1][j-1],dp[i+1][j] ) , max( dp[i+1][j],dp[i+1][j+1] ) );29 }30 }31 cout << dp[0][5] << endl;32 }33 return 0;34 }
再去撸一把 差不多就快到 2点半了 碎觉,....
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。