http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=11975#problem/D
用f【i】【j】表示i号城堡到j号城堡所需要的魔法值。
首先要用floyd算出任意两个城市之间到达所需要的最小魔法值。
然后用t【i】【j】表示i号城堡从j-1号房间到达j号房间所需要的时间。
用dp【k】【i】【j】表示当前魔法值为k到达i号城堡j号房间所需要的最短时间。
如果已经知道了dp【k】【i】【j】那么我们就可以推出dp【k】【i】【j+1】，也可以推出dp【temp】【l】【j+1】（其中l是另一个城堡，temp是当期魔法值减去i号
城堡到j号城堡所需要的魔法值。其中l！=i我们需要枚举l。
本题
#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> #define inf 0x7fffffff using namespace std; int dp[150][20][150]; int f[20][20]; int t[20][150]; int main() { int test; int n,m,z; cin>>test; for(int p=1;p<=test;p++) { cin>>n>>m>>z; for(int i=1;i<=m;i++) for(int j=2;j<=n;j++) cin>>t[i][j]; for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) cin>>f[i][j]; for(int k=1;k<=m;k++) for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(i!=j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); memset(dp,-1,sizeof(dp)); dp[z][1][1]=0; for(int i=2;i<=m;i++) { int temp=z-f[1][i]; if(temp>=0) { dp[temp][i][1]=0; } } for(int j=1;j<n;j++) { for(int k=0;k<=z;k++) { for(int i=1;i<=m;i++) if(dp[k][i][j]!=-1) { if(dp[k][i][j+1]==-1||dp[k][i][j+1]>dp[k][i][j]+t[i][j+1]) dp[k][i][j+1]=dp[k][i][j]+t[i][j+1]; for(int l=1;l<=m;l++) if(l!=i) { int temp=k-f[i][l]; if(temp>=0) { int ans=dp[k][i][j]+t[l][j+1]; if(dp[temp][l][j+1]==-1||dp[temp][l][j+1]>ans) dp[temp][l][j+1]=ans; } } } } } int ans=inf; for(int i=1;i<=m;i++) for(int k=0;k<=z;k++) if(dp[k][i][n]!=-1) ans=min(ans,dp[k][i][n]); cout<<ans<<endl; } return 0; }
是属于那种知道当前状态去递推后一种状态的情况。