【poj1010】 STAMPS

http://poj.org/problem?id=1010 (题目链接)

感到了英语深深的恶意。。。

题意（真的很难懂。。。。）

　　第一行数字是邮票的面值，每一个数字就是一个不同的种类，哪怕面值相同。以0结束。第二行数字是顾客所需要的邮票总面值。每个数字就是一个顾客的需求，以0结束。每两行是一组case。顾客是集邮爱好者，所以你必须尽可能的给他不同种类的邮票。但是一位顾客最多只能拿4张邮票。显然，我们拥有的邮票就是第一行中的数据。 
　　关于tie： 
　　　　满足顾客需求的解就是可行解。 
　　　　邮票种类最多的可行解为最优。 
　　　　如果存在两个以上的最优解的邮票种类是一样的，张数最少的更优 
　　　　张数也一样的话，这些最优解中最大面值较大的更优。 
　　　　若邮票种类、张数、最大面值三者都分别相同，则认为这些最优解相同，输出tie。 
　　　　没有解就是none。

Solution

　　这不就是裸的dfs吗。。加几个可行性剪枝就可以轻松过了。

代码

// poj1010

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#define MOD 1000000007

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    LL x=0,f=1;char ch=getchar();

    while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=10010;

int a[maxn],ans[maxn],t[maxn],b[maxn],vis[maxn];

int n,m,flag;

void work3() {

    int t1=0,t2=0;

    for (int i=1;i<=4;i++) {

        t1=max(a[t[i]],t1);

        t2=max(a[ans[i]],t2);

    }

    if (t1>t2) {flag=3;for (int i=0;i<=n;i++) ans[i]=t[i];}

    else if (t1==t2) flag=4;

}

void work2() {

    int t1=4,t2=4;

    for (int i=1;i<=4;i++) {

        if (t[i]==0) t1--;

        if (ans[i]==0) t2--;

    }

    if (t1<t2) {flag=2;for (int i=0;i<=n;i++) ans[i]=t[i];}

    else if (t1==t2) work3();

}

void work1() {

    t[0]=0;

    for (int i=1;i<=n;i++) vis[i]=0;

    for (int i=1;i<=4;i++) if (t[i] && !vis[t[i]]) {vis[t[i]]=1;t[0]++;}

    if (ans[0]<t[0]) {flag=1;for (int i=0;i<=4;i++) ans[i]=t[i];}

    else if (ans[0]==t[0]) work2();

}

void dfs(int x,int p,int w,int W) {

    if (x==5) {

        if (w==W) work1();

        return;

    }

    if (w>=W || w+(4-x+1)*a[n]<W) return;

    for (int i=p;i<=n;i++) {

        t[x]=i;

        dfs(x+1,i,w+a[i],W);

    }

}

int main() {

    while (1) {

        n=m=1;

        while (scanf("%d",&a[n])!=EOF && a[n]) n++;

        if (n==1) break;

        n--;

        while (scanf("%d",&b[m])!=EOF && b[m]) m++;

        m--;

        sort(a+1,a+1+n);

        for (int i=1;i<=m;i++) {

            for (int j=0;j<=4;j++) ans[j]=0;

            printf("%d ",b[i]);

            flag=0;

            dfs(1,0,0,b[i]);

            if (flag==4) printf("(%d): tie\n",ans[0]);

            else if (flag==0) printf("---- none\n");

            else {

                printf("(%d):",ans[0]);

                for (int i=1;i<=4;i++) if (ans[i]) printf(" %d",a[ans[i]]);

                printf("\n");

            }

        }

    }

    return 0;

}