[Vijos1747] 不给糖就捣乱

2014-07-11
竞赛题解 / 动态规划
Vijos

描述 Description

万圣节就要到了。孩子们装扮成各种恐怖的样子，挨家挨户按响邻居的门铃，大喊：“Trick or Treat!（不给糖就捣乱）”。

XX 准备了许多奇特有趣的面具——为了晚上的假面舞会，同时为了防止被孩子们捣乱，XX 准备了万圣节糖果来发给索要糖果的孩子们。

XX 有 N 种糖果罐，第 i 种糖果罐有 a[i] 颗糖果。每当有孩子来讨糖果时，他会将从中选出若干不同种类的糖果罐，使得其中的糖果总数恰好等于孩子讨要的糖果数；否则，孩子将无法得到糖果，而 XX 的假面舞会也将无法顺利的进行。

例如，XX 有 4 种糖果罐，分别有 1，4，5，5 个糖果。那么他只能提供 1，4，5，6，9，10，11，14，15 这些数量的糖果。

现在 XX 可以调整其中一种糖果罐中糖果的数量为任意正整数，他想要能够提供的不同糖果数量尽可能多，也就是尽可能满足更多孩子的需求。问：

1. 应该调整哪一种糖果罐，如果有多个最优的糖果罐可以调整，应该调整编号最小的糖果罐。

2. 经过最优化调整之后该种糖果罐应该有多少个糖果，如果有多个最优调整方法，请使调整后该种糖果罐中糖果数最少（调整后的数量可以与调整前的数量相等）。

输入格式 InputFormat

第一行是一个整数 N，表示糖果罐种数。
下面 N 行，每行 a[i] 表示第 i 种糖果罐中糖果数。

输出格式 OutputFormat

输出包括 2 行，每行一个整数，分别表示两问的答案。

样例输入 SampleInput

4
1
4
5
5

样例输出 SampleOutput

3
2

数据范围和注释 Hint

本题总共有 10 组数据，每组数据 10 分。
第一组——第三组：1<=N<=20，1<=a[i]<=20。
第四组——第六组：1<=N<=100，1<=a[i]<=7000，且 a[i] 均为偶数。
第七组——第十组：1<=N<=100，1<=a[i]<=7000。

来源 Source

Boi2010

Vijos 1747

代码 Code

两问都是 DP。第一问 f[i] 表示组成 i 个糖果的方案中糖果最小果罐编号的最大值；第二问 g[i][j] 表示前 i 个糖果罐差值是否可能为 j（背包 DP）。

原题样例第二问是闹哪样~~(>_<)~~

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define g(i,j) G[i][j+1000000]
const int inf=0x7fffffff;
int a[205];
int f[700005];
bool G[2][1700005];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
    scanf("%d",&n);m=0;
    for (i=1;i<=n;i++) scanf("%d",&a[i]),a[n+i]=a[i],m+=a[i];
    z=0;
    for (i=1;i<=2*n-1;i++)
    {
        for (j=m;j>=a[i];j--) f[j]=max(f[j],f[j-a[i]]);
        f[a[i]]=i;
        if (i<n) continue;
        x=0;y=i-n+1;
        for (j=1;j<=m;j++) if (f[j]>y) x++;
        if (x>z)
        {
            z=x;k=y;
        }
    }
    printf("%d\n",k);
    a[k]=0;
    g(0,0)=true;
    for (i=1;i<=n;i++) for (j=0;j<=m;j++) g(i&1,j)=g((i&1)^1,j) | g((i&1)^1,j-a[i]) | g((i&1)^1,j+a[i]);
    for (i=1;i<=m;i++) if (!g(n&1,i)) break;
    printf("%d\n",i);
    return 0;
}