BZOJ 2287 POJ Challenge 消失之物 分治+背包

BZOJ 2287 POJ Challenge 消失之物 分治+背包

題目大意：給定n個物品，每個物品有一個體積，對於所有的1≤i≤n,1≤j≤m輸出在不使用第i個物品的情況下裝滿大小為j的背包的方案數

我這傻逼居然真的去寫了分治背包……
第i個物品存在的時間為[1,i?1]和[i+1,n]兩個區間
然後分治……
時間復雜度O(n2logn)
黃學長我仰慕您

#include 
#include 
#include 
#include 
#include 
#define M 2020
using namespace std;
struct abcd{
    int l,r,x;
    abcd() {}
    abcd(int _,int __,int ___):
        l(_),r(__),x(___) {}
};
int n,m;
void Divide_And_Conquer(int x,int y,vector &v,vector a)
{
    int i,j,mid=x+y>>1;
    vector l,r;
    for(i=0;i<(signed)v.size();i++)
    {
        abcd temp=v[i];
        if(temp.l==x&&temp.r==y)
            for(j=m;j>=temp.x;j--)
                (a[j]+=a[j-temp.x])%=10;
        else if(temp.r<=mid)
            l.push_back(temp);
        else if(temp.l>mid)
            r.push_back(temp);
        else
            l.push_back(abcd(temp.l,mid,temp.x)),r.push_back(abcd(mid+1,temp.r,temp.x));
    }
    if(x==y)
    {
        for(i=1;i<=m;i++)
            printf("%d",a[i]);
        puts("");
        return ;
    }
    Divide_And_Conquer(x,mid,l,a);
    Divide_And_Conquer(mid+1,y,r,a);
}
int main()
{
    int i,x;
    cin>>n>>m;
    vector v;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(i!=1)
            v.push_back(abcd(1,i-1,x));
        if(i!=n)
            v.push_back(abcd(i+1,n,x));
    }
    vector a(m+1,0);a[0]=1;
    Divide_And_Conquer(1,n,v,a);
    return 0;
}