HOJ 13828 Funfair

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

Problem description

We are going to a funfair where there are n games G₁,...,G_n. 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 x₀ Oshloobs of money. If before playing game G_i, we have x Oshloobs and we win in G_i, our money increases to x+A_i for some A_i ⩾ 0. If we have x Oshloobs before playing game G_i and we lose in G_i, we lose L_i percent of x. The probability that we win game G_i (independently of other games) is P_i 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 x₀ (1 ⩽ k ⩽ n ⩽ 100, 0 ⩽ x₀ ⩽ 10⁶). Each of the next n lines specifies the properties of game G_i with three space-separated integers A_i, L_i, and P_i (0 ⩽ A_i,L_i,P_i ⩽ 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

Sample Output

117.00
112.00

思路：dp；

场上想到了dp，但是排序处理的不好所以一直没有A掉；现在改了一下…………

赢: (Ai + x) * Pi
输: (1 - Pi)(1 - Li) * x
那我过完这一关剩余钱的期望是（1 - Li + LiPi） * x + Ai * Pi
假设 c = （1 - Li + LiPi）
    d = Ai * Pi
即: cx + d
那么，在考虑先过A关还是B关的时候，有两种可能性，
先过A关：c2 * (c1*x+d1) + d2;
先过B关：c1 * (c2*x+d2) + d1;
假设A大于B，c2 * (c1*x+d1) + d2 > c1 * (c2*x+d2) + d1
所以只需按此关系排序即可；然后开始dp；
转移方程：

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);
}

具体详见代码：

#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
",dp[n][k]);
    }
    return 0;
}