首页 > 代码库 > hdu--1176---dp

hdu--1176---dp

2024-07-15 04:53:59   223人阅读

这题的题意 一定要好好理解----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 }
View Code

 

 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 }
View Code

 

再去撸一把 差不多就快到 2点半了 碎觉,....

 


联系
我们