首页 > 代码库 > hdu 5074 相邻数和最大dp
hdu 5074 相邻数和最大dp
http://acm.hdu.edu.cn/showproblem.php?pid=5074
给定一个序列 有些位数未知,给你所有两个数连续所得到的能量,问你怎么安排数字使得总能量最大
二维dp,dp[i][j]表示第i位放音符j
分类讨论即可
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <queue> #include <stack> #include <iostream> #include <algorithm> using namespace std; #define RD(x) scanf("%d",&x) #define RD2(x,y) scanf("%d%d",&x,&y) #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define clr0(x) memset(x,0,sizeof(x)) typedef long long LL; const int maxn = 105; int n,m,s[maxn][maxn],p[maxn]; int dp[maxn][maxn];//i位,此位j int main() { int _;RD(_);while(_--){ RD2(n,m); for(int i = 1;i <= m;++i) for(int j = 1;j <= m;++j){ RD(s[i][j]); } for(int i = 1;i <= n;++i) RD(p[i]); clr0(dp); for(int i = 1;i < n;++i){ if(p[i] > 0){ if(p[i+1] > 0) dp[i+1][p[i+1]] = dp[i][p[i]] + s[p[i]][p[i+1]]; else for(int j = 1;j <= m;++j) dp[i+1][j] = max(dp[i+1][j],dp[i][p[i]] + s[p[i]][j]); } else{ if(p[i+1] > 0) for(int j = 1;j <= m;++j) dp[i+1][p[i+1]] = max(dp[i+1][p[i+1]],dp[i][j] + s[j][p[i+1]]); else for(int j = 1;j <= m;++j) for(int k = 1;k <= m;++k) dp[i+1][j] = max(dp[i+1][j],dp[i][k] + s[k][j]); } } int ans = 0; for(int i = 1;i <= m;++i) ans = max(ans,dp[n][i]); printf("%d\n",ans); } return 0; }
hdu 5074 相邻数和最大dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。