程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj2287【POJ Challenge】消失之物

bzoj2287【POJ Challenge】消失之物

編輯:C++入門知識

bzoj2287【POJ Challenge】消失之物


Description

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

\

Input

第1行:兩個整數N(1 ≤N≤ 2 × 103) 和M(1 ≤M≤ 2 × 103),物品的數量和最大的容積。

第2行:N個整數W1,W2, ...,WN, 物品的體積。

Output

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

Sample Input

3 2
1 1 2

Sample Output

11
11
21

HINT

如果物品3丟失的話,只有一種方法裝滿容量是2的背包,即選擇物品1和物品2。

Source

思路很不錯的DP題,又沒有想出來做法...QAQ

f[i][j]表示前i個物品,裝滿容積為j的背包的方案數。

顯然f數組是可以用O(n^2)的DP計算出的。

g[i][j]表示不選第i個物品,裝滿容積為j的背包的方案數。

如果j

如果j≥n,則g[i][j]=f[n][j]-g[i][j-w[i]]。

可以發現f和g數組都可以用一維實現。

一開始WA了很多次,因為沒有每一步都取模。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 2005
using namespace std;
int n,m;
int f[maxn],g[maxn],w[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();m=read();
	F(i,1,n) w[i]=read();
	memset(f,0,sizeof(f));
	f[0]=1;
	F(i,1,n) D(j,m,w[i]) f[j]+=f[j-w[i]];
	F(i,1,n)
	{
		F(j,0,w[i]-1) g[j]=f[j];
		F(j,w[i],m) g[j]=f[j]-g[j-w[i]];
		F(j,1,m) printf("%d",g[j]%10);
		printf("\n");
	}
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved