首页 > 代码库 > hdu 5074 DP 2014鞍山现场赛题
hdu 5074 DP 2014鞍山现场赛题
hdu 5074 http://acm.hdu.edu.cn/showproblem.php?pid=5074
挺水的DP,注意依a[i-1]和a[i]的正负区分状态转移,然后O(n^3)即可轻易解决,我DP挺弱的也能过,貌似也就CF C题水平
//#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <iomanip> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdout) const ll ll_INF = ((ull)(-1))>>1; const double EPS = 1e-8; const double pi = acos(-1.0); const ll INF = 1e18; const int MAXN = 100+10; int mat[MAXN][MAXN]; ll dp[MAXN][MAXN]; int a[MAXN]; int n,m; ll solve() { for(int i=2;i<=n;i++) { if(a[i]>0) { if(a[i-1]>0) dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][a[i-1]]+mat[a[i-1]][a[i]]); else for(int k=1;k<=m;k++) dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][k]+mat[k][a[i]]); } else { if(a[i-1]>0) { for(int j=1;j<=m;j++) dp[i][j]=max(dp[i][j],dp[i-1][a[i-1]] + mat[a[i-1]][j]); } else { for(int j=1;j<=m;j++) { for(int k=1;k<=m;k++) dp[i][j]=max(dp[i][j],dp[i-1][k]+mat[k][j]); } } } } ll ans=0LL; for(int i=1;i<=m;i++) ans=max(ans,dp[n][i]); return ans; } int main() { //IN("hdu5074.txt"); int ncase; scanf("%d",&ncase); while(ncase--) { scanf("%d%d",&n,&m); CL(mat,0); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) scanf("%d",&mat[i][j]); a[0]=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); CL(dp,0); printf("%I64d\n",solve()); } return 0; }
hdu 5074 DP 2014鞍山现场赛题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。