首页 > 代码库 > UVALive 4731 dp+贪心

UVALive 4731 dp+贪心

2024-07-13 13:07:21   223人阅读

这个题首先要利用题目的特性，先贪心，否则无法进行DP

因为求期望的话，越后面的乘的越大，所以为了得到最小值，应该把概率值降序排序，把大的数跟小的系数相乘

然后这种dp的特性就是转移的时候，由 i推到i+1每次添加一个数，就要考虑这个新数应该和谁放在一组，枚举他放在哪一组即可

dp[i][j]代表当前第i个数有j个分组时候的最小值

dp[i][j]=dp[k][j-1]+i(prefix[i]-prefix[k-1]),k代表枚举第几个数开始和当前新添加的数为一组，prefix为前缀和，为了迅速得出区间和

注意边界处理和一些细节

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <set>#define LL __int64using namespace std;struct node{    int x,y;    bool operator < (const node&rhs) const    {        if (x==rhs.x) return y<rhs.y;        return x<rhs.x;    }}tasks[100010];bool cmp(node a,node b){    if (a.x==b.x) return a.y<b.y;    return a.x<b.x;}int n,m;multiset<node> v;multiset<node>::iterator it;/*int bs(int p,int q){    int L=0,R=v[p].size(),mid;    while (L<R)    {        mid=(L+R)>>1;        if (v[p][mid]<tasks[q].x) L=mid+1;        else R=mid;    }    return L;}*/int main(){    int a,b;    while (scanf("%d%d",&m,&n)!=EOF)    {        int maxn=0;        v.clear();        for (int i=1;i<=m;i++){            scanf("%d%d",&a,&b);            v.insert((node){a,b});            maxn=max(b,maxn);        }        for (int i=1;i<=n;i++){            scanf("%d%d",&a,&b);            tasks[i].x=a;            tasks[i].y=b;        }        sort(tasks+1,tasks+1+n);        //for (int i=0;i<=maxn;i++) sort(v[i].begin(),v[i].end());        LL ans=0;        int sum=0;        for (int i=n;i>=1;i--){            it=v.lower_bound(tasks[i]);                if (it==v.end()) continue;                else{                    v.erase(it);                    ans+=(LL)tasks[i].x*500+(LL)tasks[i].y*2;                    sum++;                }        }        printf("%d %I64d\n",sum,ans);    }    return 0;}

　　


联系
我们