首页 > 代码库 > hdu--2571--dp
hdu--2571--dp
Ah...day by day...
今天 看到公公建立个新生 程序群 想起了去年夏天 自己刚刚得知是计科的时候 的 一片茫然。。
记得 去看了视频学了下C 发现太难了啊 又去学了下java 发现还是java的入门比C简单啊。。。
反正 现在快忘光了 =-=
我只想和学弟学妹们说： 慢慢来 不用急着问 哪本书适合入门 It‘s a long long road
-----------------------
还是喜欢讲点碎碎念 发牢骚=-=、
这题 要是让我很久前做肯定以为是dfs的...
这题 其实和数塔什么的都有一点共同之处的。。
dp[ i ][ j ] += max( dp[ i-1 ] [ j ] , dp[ i ] [ j-1 ] , dp [ i , j*k ] )...至于边界处理 这边就不注明了 反正这个状态方程就是本题的核心
一开始 想先A掉 开了2个数组 方便理解 后来 就用了一个数组
反正 每道题自己能做到如何优化 就尽量优化它 要是遇到 数据太大嘛。。
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int inf = -0x3f3f3f3f; 6 int maze[25][1010]; 7 int dp[25][1010]; 8 9 int main()10 {11 int t , n , m;12 while( cin >> t )13 {14 while( t-- )15 {16 cin >> n >> m;17 for( int i = 1 ; i<=n ; i++ )18 {19 for( int j = 1 ; j<=m ; j++ )20 {21 cin >> maze[i][j];22 }23 }24 for( int i = 0 ; i<=n ; i++ )25 dp[i][0] = inf;26 for( int j = 0 ; j<=m ; j++ )27 dp[0][j] = inf;28 dp[0][1] = dp[1][0] = 0;29 for( int i = 1 ; i<=n ; i++ )30 {31 for( int j = 1 ; j<=m ; j++ )32 {33 dp[i][j] = max( dp[i-1][j] , dp[i][j-1] );34 for( int k = 1 ; k<j ; k++ )35 {36 if( j%k==0 )37 dp[i][j] = max( dp[i][j] , dp[i][k] );38 }39 dp[i][j] += maze[i][j];40 }41 }42 cout << dp[n][m] << endl;43 }44 }45 return 0;46 }
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int inf = -0x3f3f3f3f; 6 int dp[25][1010]; 7 8 int main() 9 {10 int t , n , m , temp;11 while( cin >> t )12 {13 while( t-- )14 {15 cin >> n >> m;16 for( int i = 1 ; i<=n ; i++ )17 {18 for( int j = 1 ; j<=m ; j++ )19 {20 cin >> dp[i][j];21 }22 }23 for( int i = 1 ; i<=n ; i++ )24 {25 for( int j = 1 ; j<=m ; j++ )26 {27 temp = inf;28 if( i==1 && j==1 )29 continue;30 else if( i>=2 && j==1 )31 temp = max( temp , dp[i-1][j] );32 else if( i==1 && j>=2 )33 temp = max( temp , dp[i][j-1] );34 else35 temp = max( dp[i-1][j] , dp[i][j-1] );36 for( int k = 1 ; k<j ; k++ )37 {38 if( j%k==0 )39 temp = max( temp , dp[i][k] );40 }41 dp[i][j] += temp;42 }43 }44 cout << dp[n][m] << endl;45 }46 }47 return 0;48 }
today:
同学聚会 才过了一年 大家就默契地定在了宾馆下的酒店 =-=
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。