[POJ1009] 消失之物

题面:

传送门:POJ


Solution

DP+DP

首先,我们可以很轻松地求出所有物品都要的情况下的选择方案数,一个简单的满背包DP就好

即:$f[i][j]$表示前i个物品装满容量为j的背包的方案数.

转移也很简单 $f[i][j]=f[i-1][j]+f[i-1][j-w[i]] (i:1~n,j:1~m)$ (即选和不选的问题)

初始化 $f[i][0]=1 (i:[0~n])$ (如果背包容量为0,无论如何都有且只有一种方案将其装满)

接下来,考虑用另一个dp来求解在某一物品不放下的方案数

设 $g[i][j]$ 表示第i个物品不放入背包,装满容量为j的背包的方案数

转移为:

$g[i][j] = f[n][j] ( j < w[i]) $ (即当背包容量小于所不放物品的大小时,那么其方案数必然为f[n][j],因为f[n][j]中的所有方案肯定取不到第i个)

   $= f[n][j] - g[i][j-w[i]]$ i:1-nj:1-m

下面那个转移意思即是:

所有的方案总数 减去 包括第i项物品的方案数

因为$g[i][j-w[i]]$中的每一种情况再装入$w[i]$即可达到$g[i][j]$这个状态,而$g[i][j]$的定义是不装入i的方案数,所以说包括第i项物品的方案能且仅能从$g[i][j-w[i]]$转移过来

初始化:

$g[i][0]=1$ (i:[0~n])(背包容量为0时方案有且仅有啥都不要)

这样就可以口头AC了

但是,还有一个要注意的小地方

在%P的意义下, $f[n][j]-g[i][j-w[i]]$有可能为负数

负数取模的方法为 : $(x\ mod\ P + P)mod\ P$

然后就OK啦


Code

//Openjudge 1009:消失之物
//Apr,2ed,2018
//DP+DP
#include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=2000+100;
const int M=2000+100;
const int P=10;
char f[N][M],g[M];
int w[N],n,m;
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        w[i]=read();

    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j-w[i]>=0)
                f[i][j]+=f[i-1][j-w[i]];
            if(f[i][j]>=P) f[i][j]%=P;
        }

    g[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j<w[i])
                printf("%d",g[j]=f[n][j]);
            else
                printf("%d",g[j]=(f[n][j]-g[j-w[i]]+P)%P);
        }
        printf("\n");
    }
    return 0;
}


后记

这种DP+DP的题目还是第一次写,写起来有一点点不熟练

看来我还是需要多学习一个

点赞
  1. WarmSnow说道:
    Google Chrome 63.0.3239.132 Google Chrome 63.0.3239.132 Windows XP Windows XP

    EEEEEeeeee

    1. GoldenPotato137说道:
      Google Chrome 71.0.3578.98 Google Chrome 71.0.3578.98 Windows 10 x64 Edition Windows 10 x64 Edition

      诶?

  2. WarmSnow说道:
    Google Chrome 63.0.3239.132 Google Chrome 63.0.3239.132 Windows 10 x64 Edition Windows 10 x64 Edition

    Good !

发表评论

电子邮件地址不会被公开。必填项已用 * 标注