题解 P2306 【被yyh虐的mzc】

· · 题解

解法一：

这题的m，n超级大， n,m<=100000

单纯的01背包肯定会TLE但是，ai和bi非常小，只ai,bi<=10 我们要如何利用ai和bi呢？

我们仔细的想一想后会发现：ai和bi一定会重复多次出现

我们可以用一个二维数组t来记录ai和bi的出现次数

然后利用二进制的思想，把t[ai][bi]个aibi分成1，2，4.....个aibi

（因为这样可以通过相加得到1到t[ai][bi]个ai，bi。但只要log（t[ai][bi]）左右的时间可做到）

例如把20分成 1 2 4 8 5

这样做了之后，我们就可以做01背包了 

#include<cstdio>
#include<algorithm>//这头文件有max 函数 
using namespace std;
struct lol{int a,c;} d[100010];//d[i].a相当于ai ,d[i].c相当于bi
int f[100010],t[11][11],len=0;
int main()
{
    int n,m,k;scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        int x,y;scanf("%d %d",&x,&y);
        if(t[x][y]==0){d[++len].a=x;d[len].c=y;}//可同下同时删除 
        t[x][y]++;//统计aibi的出现次数 
    }
    for(int x=0;x<=10;x++)
    {
        for(int y=0;y<=10;y++)
        {
            int v=1;
            --t[x][y];//可同上同时删除 
            while(t[x][y]>=v){d[++len].a=x*v;d[len].c=y*v;t[x][y]-=v;v*=2;} 
            //利用二进制思想分 ，len统计个数 
            if(t[x][y]>0){d[++len].a=x*t[x][y];d[len].c=y*t[x][y];t[x][y]=0;}
            //把剩下存进来 
        }
    }
    /////////////////////////01背包 
    for(int i=1;i<=len;i++)
    {
        for(int j=m;j>=d[i].a;j--)
        {
            f[j]=max(f[j],f[j-d[i].a]+d[i].c);
        }
    }
    if(f[m]>=k)printf("yes\n");
    else printf("no\n");
    printf("%d",f[m]);
}

解法二： o3+o2+01背包（黑科技）