2287: 【POJ Challenge】消失之物

Description

ftiasch 有?N?個物品, 體積分別是?W₁,?W₂, ...,?W_N。 由于她的疏忽, 第?i?個物品丟失了。 “要使用剩下的?N?- 1 物品裝滿容積為?x?的背包，有幾種方法呢？” -- 這是經典的問題了。她把答案記為?Count(i, x)?，想要得到所有1 <= i <= N, 1 <= x <= M的?Count(i, x)?表格。

Input

第1行：兩個整數?N?(1 ≤?N?≤ 2 × 10³) 和?M?(1 ≤?M?≤ 2 × 10³)，物品的數量和最大的容積。

第2行：?N?個整數?W₁,?W₂, ...,?W_N, 物品的體積。

Output

一個?N?×?M?的矩陣，?Count(i, x)的末位數字。

Sample Input

3 2
1 1 2

Sample Output

11
11
21

HINT

?解析：首先我們先不要考慮是否會有一個物品消失，直接先用f數組來表示到第i個物品時，能達到j的重量的方案有多少，然后用一個c數組來表示所有物品中，除去第i個物品，能達到j的重量的方案有多少，c[i][j]=f[n][j]-c[i][j-a[i]]（c[i][j-a[i]]指除去第i個物品中能達到j-a[i]重量的方案數即其他物品加上a[i]（即算上第i個物品）后能達到j的重量的方案數，減去后，剩下的就是，不用第i個物品達到j的方案數）;(a[i]表示當前物品的重量)具體步驟看程序。

ps:因為題目要求輸出個位數，所以過程中必須取余10，但是在后面個位數減去個位數會造成負數的情況，所以在一些地方需要+10后再運算。

#include<iostream>
#include<cstdio>
using namespace std;
long long f[2005][2005],w[3000],b[2005][2005],x,n,m;
int main()
{cin>>n>>m;for (int i=1;i<=n;i++) cin>>w[i];for (int i=0;i<=n;i++)for (int j=0;j<=m;j++)f[i][j]=0,b[i][j];f[0][0]=1;//剛開始前0個物品達到0的重量的方案數為一for (int i=1;i<=n;i++)for (int j=0;j<=m;j++)if (j-w[i]>=0) f[i][j]+=(f[i-1][j-w[i]]+f[i-1][j])%10;//取或不取的方案數都加上else f[i][j]+=f[i-1][j]%10;for (int i=1;i<=n;i++)for (int j=0;j<=m;j++)if (j-w[i]>=0) b[i][j]=(f[n][j]-b[i][j-w[i]]+10)%10;//不取第i個物品的達到j的重量的方案數由此得出，加10是為了避免個位與個位相減時出現負數。else b[i][j]=f[n][j]%10;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (j!=m) cout<<b[i][j];else cout<<b[i][j]<<endl;//輸出return 0;
}

好啦

?