都说这一题是签到题。。可我怎么签了这么久。。
dp问题,dp[i][j]表示填到了第i个位置,填数字i,然后,dp[i][j]=max(dp[i][j],dp[i-1][k]+p[k][j]) ,k枚举了所有的数字
要考虑a[i]!=-1的情形,如果a[i]!=-1,则状态只需要转移到dp[i][a[i]],其他的dp[i][j]跳过,因为dp初始值是-INF,转移到dp[i+1][j]的时候也只会从dp[i][a[i]]转移。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> using namespace std; //hdu 5074 int T; int n; int m; int p[55][55]; int a[110]; int dp[110][55];//dp[i][j] means填到第i位置,填j数 int ans; int INF=0x3f3f3f3f;//1061109567; void run() { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { dp[i][j]=-INF; } } // for(int i=1;i<=m;i++) cout<<dp[1][a[i]]<<endl; ans=0; if(a[1]==-1) { for(int i=1;i<=m;i++) { dp[1][i]=0; } } else { dp[1][a[1]]=0; } for(int i=2;i<=n;i++) { for(int k=1;k<=m;k++) { if(a[i]!=-1) { dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][k]+p[k][a[i]]); // cout<<i<<" "<<a[i]<<" "<<k<<" "<<dp[i][a[i]]<<" "<<p[k][a[i]]<<" "<<dp[i-1][k]<<endl; } else { for(int j=1;j<=m;j++) { { dp[i][j]=max(dp[i][j],dp[i-1][k]+p[k][j]); } } } } } for(int i=1;i<=m;i++) { ans=max(ans,dp[n][i]); } printf("%d\n",ans); } int main() { freopen("input.txt","r",stdin); // freopen("data.txt","r",stdin); // freopen("out1.txt","w",stdout); scanf("%d",&T); for(int t=0;t<T;t++) { memset(p,0,sizeof(p)); memset(a,0,sizeof(a)); scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { for(int j=1;j<=m;j++) { scanf("%d",&p[i][j]); } } for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } run(); } return 0; }