鏈接：http://acm.hnu.cn/online/?action=problem&type=show&id=13828

Problem description

We are going to a funfair where there are n games G1,...,Gn. We want to play k games out of the n games, and we can choose the order in which we play them—note that we cannot play any game more than once. We have to specify these k games and their order before starting any game. At each point in time, we have some amount of money, which we use in playing the games. At the beginning, we have x0?Oshloobs of money. If before playing game Gi, we have x Oshloobs and we win in Gi, our money increases to x+Ai?for some Ai?? 0. If we have x Oshloobs before playing game Gi?and we lose in Gi, we lose Li?percent of x. The probability that we win game Gi?(independently of other games) is Pi?percents. The goal is to play k of the games in such an order to maximize the expected amount of money we end up with after playing all k selected games in that order.

Input

There are multiple test cases in the input. The first line of each test case contains three space-separated integers n, k, and x0?(1 ? k ? n ? 100, 0 ? x0?? 106). Each of the next n lines specifies the properties of game Gi?with three space-separated integers Ai, Li, and Pi?(0 ? Ai,Li,Pi?? 100). The input terminates with a line containing 0 0 0 which should not be processed.

Output

For each test case, output a single line containing the maximum expected amount of our final money rounded to exactly two digits after the decimal point.

Sample Input

2 2 100 10 0 50 100 10 20 2 1 100 10 0 50 100 10 20 0 0 0

Sample Output

117.00 112.00

思路：dp；

場(chǎng)上想到了dp，但是排序處理的不好所以一直沒(méi)有A掉；現(xiàn)在改了一下…………

贏(yíng): (Ai + x) * Pi 輸: (1 - Pi)(1 - Li) * x 那我過(guò)完這一關(guān)剩余錢(qián)的期望是（1 - Li + LiPi） * x + Ai * Pi 假設(shè) c = （1 - Li + LiPi）d = Ai * Pi 即: cx + d 那么，在考慮先過(guò)A關(guān)還是B關(guān)的時(shí)候，有兩種可能性， 先過(guò)A關(guān)：c2 * (c1*x+d1) + d2; 先過(guò)B關(guān)：c1 * (c2*x+d2) + d1; 假設(shè)A大于B，c2 * (c1*x+d1) + d2 > c1 * (c2*x+d2) + d1
所以只需按此關(guān)系排序即可；然后開(kāi)始dp；
轉(zhuǎn)移方程：

if(j==i) dp[i][j]=c*dp[i-1][j-1]+d;
else
{
dp[i][j]=max(dp[i-1][j],c*dp[i-1][j-1]+d);
}

具體詳見(jiàn)代碼：

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int maxn=105; struct node {double a,l,p,c,d;node(double _a=0.0,double _l=0.0,double _p=0.0):a(_a),l(_l),p(_p){c=1-l+l*p;d=a*p;}bool operator <(const node &r)const{return d*r.c+r.d>r.d*c+d;} }; node ga[maxn]; double dp[maxn][maxn];int main() {freopen("input.txt","r",stdin);int n,k;double x0;while(scanf("%d%d%lf",&n,&k,&x0),n){int nw=0,nl=0;for(int i=1;i<=n;i++){double ta,tl,tp;scanf("%lf%lf%lf",&ta,&tl,&tp);ga[i]=node(ta,tl/100.0,tp/100.0);}memset(dp,0,sizeof dp);sort(ga+1,ga+1+n);for(int i=0;i<=n;i++)dp[i][0]=x0;for(int i=1;i<=n;i++){int s=min(k,i);double c=ga[i].c,d=ga[i].d;for(int j=1;j<=s;j++){if(j==i) dp[i][j]=c*dp[i-1][j-1]+d;else{dp[i][j]=max(dp[i-1][j],c*dp[i-1][j-1]+d);}}}printf("%.2lf\n",dp[n][k]);}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/MeowMeowMeow/p/7299208.html

總結(jié)

以上是生活随笔為你收集整理的HOJ 13828 Funfair的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。