首页 > 代码库 > 二维dp(O(N^3)实现) zoj3230
二维dp(O(N^3)实现) zoj3230
1 #include<iostream> 2 #include<string.h> 3 #include<stdio.h> 4 #define maxn 125 5 using namespace std; 6 7 int cost[maxn][maxn],w[maxn][maxn]; 8 int dp[maxn][maxn]; 9 int N,M; 10 int main(){ 11 while(cin>>N>>M){ 12 if (N==0 && M==0) break; 13 for(int i=1;i<=N;i++){//meiju N 14 for(int j=1;j<=N;j++) scanf("%d",&cost[i][j]); 15 } 16 for(int i=1;i<=M;i++){ 17 for(int j=1;j<=N;j++) scanf("%d",&w[i][j]); 18 } 19 memset(dp,-1,sizeof(dp)); 20 dp[0][1]=0;//dp[i][j]:ith day jth city 21 for(int i=1;i<=N;i++) dp[1][i]=-cost[1][i]+w[1][i]; 22 for(int i=2;i<=M;i++){//da 23 for(int j=1;j<=N;j++){//stay at jth city 24 for(int k=1;k<=N;k++){//from kth city 25 dp[i][j]=max(dp[i][j],dp[i-1][k]-cost[k][j]+w[i][j]); 26 } 27 } 28 } 29 int ans=-(1<<(30)); 30 for(int i=1;i<=N;i++){ 31 ans=max(ans,dp[M][i]); 32 } 33 cout<<ans<<endl; 34 } 35 return 0; 36 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。