BZOJ1042 [HAOI2008]硬币购物

2014.12.10 13:37 Wed| 2 visits oi_2015| 2015_刷题日常| Text

这一次准备继续犯懒,结果……

Solution

这道题可用容斥原理解决。只要细心就没什么问题了。只是有一点点复杂……

由于边界判断不是人写的事情,最开始在旁边另外开了一个没用的数组以供边界溢出。

//我知道这样玩是不对的,两个数组在内存中分配的空间不一定是连续的。。好在,这个代码在RP好的情况下可以AC。不过千万不要效仿……

Code

#include <bits/stdc++.h>
using namespace std;

int c[5],tot;
long long e[500005],f[100005];

int main()
{
    cin>>c[1]>>c[2]>>c[3]>>c[4]>>tot;
    f[0]=1;
    for(int i=1;i<=4;i++)
        for(int j=c[i];j<=100000;j++)
            f[j]+=f[j-c[i]];
    for(int i=1;i<=tot;i++)
    {
        int d1,d2,d3,d4,s;
        long long t1,t2,t3,t4,t5,t6,ans;
        cin>>d1>>d2>>d3>>d4>>s;
        ans=f[s];
        t1=f[s-(d1+1)*c[1]]; t2=f[s-(d2+1)*c[2]];
        t3=f[s-(d3+1)*c[3]]; t4=f[s-(d4+1)*c[4]];
        ans=ans-t1-t2-t3-t4;
        t1=f[s-(d1+1)*c[1]-(d2+1)*c[2]]; t2=f[s-(d2+1)*c[2]-(d3+1)*c[3]];
        t3=f[s-(d3+1)*c[3]-(d4+1)*c[4]]; t4=f[s-(d4+1)*c[4]-(d1+1)*c[1]];
        t5=f[s-(d1+1)*c[1]-(d3+1)*c[3]]; t6=f[s-(d2+1)*c[2]-(d4+1)*c[4]];
        ans=ans+t1+t2+t3+t4+t5+t6;
        t1=f[s-(d1+1)*c[1]-(d2+1)*c[2]-(d3+1)*c[3]]; t2=f[s-(d2+1)*c[2]-(d3+1)*c[3]-(d4+1)*c[4]];
        t3=f[s-(d3+1)*c[3]-(d4+1)*c[4]-(d1+1)*c[1]]; t4=f[s-(d4+1)*c[4]-(d1+1)*c[1]-(d2+1)*c[2]];
        ans=ans-t1-t2-t3-t4;
        t1=f[s-(d1+1)*c[1]-(d2+1)*c[2]-(d3+1)*c[3]-(d4+1)*c[4]];
        ans=ans+t1;
        cout<<ans<<endl;
    }
}

另外,也可以开一个结构体解决溢出的事情。

struct O_o
{
    long long num[100005];
    long long v(int pos)
    {
        cout<<pos<<endl;
        return pos>=0?num[pos]:0;
    }
}f;

其实上面的代码同样写沙茶了……本来可以写一个函数完成这件事情的……可惜我当时没有想到……