HDU 4800 DP

本文主要是介绍HDU 4800 DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

13长沙现场赛

DP

就是告诉你C(m,3)个队伍相互之间的胜率，然后要你依次对战n个AI队伍，首先任选一种队伍，然后战胜一个AI后可以选择替换成AI的队伍，也可以不换，问你最后最大的胜率是多少。

从最后一个对战开始DP

dp[i][j]=a[j][b[i]]*max(dp[i+1][j],dp[i+1][b[i]])

#include "stdio.h"
#include "string.h"
#include "math.h"
#include "stdlib.h"double dp[10010][210];
int main()
{int m,i,j,n;double x;int b[10010];double a[210][210];while (scanf("%d",&m)!=EOF){m=m*(m-1)*(m-2)/6;for (i=0;i<m;i++)for (j=0;j<m;j++)scanf("%lf",&a[i][j]);scanf("%d",&n);for (i=1;i<=n;i++)scanf("%d",&b[i]);for (i=0;i<m;i++)dp[n][i]=a[i][b[n]];for (i=n-1;i>=1;i--){for (j=0;j<m;j++)dp[i][j]=dp[i+1][j]*a[j][b[i]];x=dp[i+1][b[i]];for (j=0;j<m;j++)if (dp[i][j]<x*a[j][b[i]])dp[i][j]=x*a[j][b[i]];}x=0;for (i=0;i<m;i++)if (dp[1][i]>x) x=dp[1][i];printf("%.6lf\n",x);}return 0;
}

这篇关于HDU 4800 DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---