HOJ Funfair

HOJ Funfair

读题坑了队友，害怕.jpg

好好做还是能a的，详见队友的博客了，大佬讲了一下，还是不难的，但是~~~

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
#define ll long long
const int maxn=110;
double dp[maxn][maxn];
struct Node
{double a,l,p;double c,d;
}nod[maxn];
bool cmp(Node A,Node B)
{return (A.c-1)*B.d<A.d*(B.c-1);
}
int  main()
{//freopen("C:\Users\Administrator\Desktop\a.txt","r",stdin);//ios::sync_with_stdio(false);//freopen("C:\Users\Administrator\Desktop\b.txt","w",stdout);int n,k;double a,l,p,x;while(scanf("%d%d%lf",&n,&k,&x),n+k+x){memset(dp,0,sizeof dp);for(int i=1;i<=n;i++){scanf("%lf%lf%lf",&a,&l,&p);l/=100.0,p/=100.0;nod[i].a=a,nod[i].l=l,nod[i].p=p;nod[i].c=(1.0+l*p-l),nod[i].d=a*p;}sort(nod+1,nod+n+1,cmp);memset(dp,-INF,sizeof dp);dp[0][0]=x;for(int i=1;i<=n;i++){dp[i][0]=x;int s=min(k,i);for(int j=1;j<=s;j++){if(i>j)dp[i][j]=dp[i-1][j];dp[i][j]=max(dp[i][j],dp[i-1][j-1]*nod[i].c+nod[i].d);}}printf("%.2lfn",dp[n][k]);}return 0;
}

转载于:.html