ZOJ 3735 dp

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3735

好久没做DP题了，一开始没理解题目里的C(M,3)是干什么，原来就是组合，C M 取3，就等于n*（n-1）*（n-2）/6;题目里还有一个细节是说电脑玩家是要一个接着一个打败，这样，规划方向也确定了，设dp[i][j]为当前打败了Ai电脑，并且阵容为j的概率最大值，dp[i][j]=max(dp[i][j],dp[i-1][j]*p[j][no[i]]) ,p[][]为对应的概率，no[]为电脑编号

此外因为某个人可以在打败某个电脑之后变成该电脑的阵容，因此又能得到一个方程 dp[i][no[i]]=max(自身，dp[i-1][j]*p[j][no[i]]);

#include <cstdio>
#include <cstring>
using namespace std;
double dp[10010][150];
int no[10010];
double p[150][150];
double max(double a,double b)
{if (a<b) return b;return a;
}
int main()
{int M,n;while(scanf("%d",&M)!=EOF){n=M*(M-1)*(M-2)/6;for (int i=0;i<n;i++){for (int j=0;j<n;j++){scanf("%lf",&p[i][j]);}}memset(dp,0,sizeof dp);int m;scanf("%d",&m);for (int i=1;i<=m;i++)scanf("%d",&no[i]);for (int i=0;i<=n;i++)dp[0][i]=1;for (int i=1;i<=m;i++){for (int j=0;j<n;j++){dp[i][j]=max(dp[i][j],dp[i-1][j]*p[j][no[i]]);dp[i][no[i]]=max(dp[i][no[i]],dp[i-1][j]*p[j][no[i]]);}}double ans=0;for (int i=0;i<n;i++){ans=max(ans,dp[m][i]);}printf("%.7f\n",ans);}return 0;
}