T1 Too Young

题面描述

大学选课真的是一件很苦恼的事呢！
Marco：“我要两年毕业！我要选尽量多的学分！这些课统统选上！”
长者："你啊，Too Young！你看看作业量，你做的完吗？"
Marco（笑容逐渐消失.gif）：”那可咋整啊?“
长者："还能咋整？退课呗！“
已知 Marco 选了门课，每门课有学分，劳累度 和挂科概率
其中，为 [1,5] 范围内的一个正整数，是 int 范围内正整数，是[0,1]范围内小数；
现在 Marco 想退掉某些课使得自己的劳累度尽量小，但是，如果 Marco 的学分总数达不到给定的 MINXMINX，他会被退学。
Marco想知道，在期望学分大于等于的情况下，他的最小劳累度是多少。
注意：如果一门课挂科，Marco 将付出的劳累度但是无法获得相应学分；否则，Marco 将付出的劳累度并收获的学分。

输入格式

第一行一个正整数表示课程数量
接下来 NN 行，每行空格分开的个数和，含义如题面所述
最后一行一个正整数表示所需最小学分。

输出格式

一行一个正整数表示最小劳累度。

样例数据

样例输入

2
1 233 0
2 1 0.5
1

样例输出

1

题解

因为p最多是两位小数，所以直接将全部扩大一百倍即可。要注意精度问题。

#include<bits/stdc++.h>
#define int long long
#define maxn 2005
using namespace std;
inline char get(){
    static char buf[30000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
} 
inline int read(){
    register char c=getchar();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();
    return _*f;
}
struct edge{
    int v,w;
    double p;
}E[maxn];
int n;
int minx,minld=0x3f3f3f3f;
int dp[2][250001];
signed main(){
    //freopen("1.txt","r",stdin);
    n=read();
    int V=0;
    for(register int i=1;i<=n;i++){
        E[i].w=read();
        E[i].v=read();
        scanf("%lf",&E[i].p);
        double cas;
        cas=(1.00-E[i].p);
        double q=E[i].w;
        cas*=q;
        cas*=100;
        cas+=0.0001;
        E[i].w=cas;
        V+=E[i].w;
    }
    //for(register int i=1;i<=n;i++)cout<<i<<" "<<E[i].w<<" "<<E[i].v<<endl;
    minx=read();
    minx*=100;
    //cout<<minx<<endl;
    for(register int i=0;i<2;i++){
        for(register int j=0;j<250001;j++)dp[i][j]=1e18;
    } 
    dp[0][0]=0;
    int tot=1e18;
    for(register int i=1,flag=1;i<=n;i++,flag ^= 1){
        for(register int j=0;j<=V;j++){
            if(j-E[i].w>=0)dp[flag][j]=min(dp[flag ^ 1][j],dp[flag ^ 1][j-E[i].w]+E[i].v);
            else dp[flag][j]=dp[flag ^ 1][j];
            if(j>=minx)tot=min(tot,dp[flag][j]);
        }
    }
    printf("%lld",tot);
    return 0;
}