[1413] Weight
時間限制: 1000 ms 內存限制: 65535 K
問題描述
有n個砝碼，每個砝碼都有各自的重量。
那麼這些砝碼一共能稱出哪些重量。
輸入
輸入一個正整數 n (1 <= n <= 100)表示一共有 n 個砝碼。
接下來一行有n個正整數，每個正整數表示該砝碼的重量，其重量不會超過100。
輸出
從小到大輸出所有可能的情況。
對於每行，包含兩個數，前面一個數是能稱出的重量，後面一個數是能稱出該重量的不同情況的數量(就算重量相等的砝碼也被視為不同的砝碼)。
其數量要對100000007求余。
樣例輸入
4
1 2 3 4
樣例輸出
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 1
9 1
10 1
提示
無來源
Hungar
思路 ：很明顯是母函數
[cpp]
#include<stdio.h>
#include<string.h>
int num[111],val[111];
int c1[10000+100],c2[10000+100];
#define mod 100000007;
int main()
{
int n,i,j,k,sum;
while(scanf("%d",&n)!=EOF)
{
sum=0;
memset(num,0,sizeof(num));
for(i=1;i<=n;i++)
{
scanf("%d",&val[i]);
num[val[i]]=1;
sum+=val[i];
}
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(j=0;j<=val[1]*num[val[1]];j+=val[1])//限制了每種的個數 最多為 num[val[i]]*val[i] 由於本題都是1 可以去掉不寫
/*如 質量為1 的砝碼有4個 則母函數第一個式子為為 1+x^1+x^2+x^3+x^4*/
c1[j]=1;
for(i=2;i<=n;i++)
{
for(j=0;j<=sum;j++)//指向上一次已經計算過的式子的項
for(k=0;k+j<=sum&&k<=num[val[i]]*val[i];k+=val[i])//限制了每種的個數就要這樣寫了
{//k指向當前要成的式子的項
c2[k+j]+=c1[j]%mod;
c2[k+j]%=mod;
}
for(k=0;k<=sum;k++)
{
c1[k]=c2[k]%mod;
c2[k]=0;
}
}
for(i=1;i<=sum;i++)
if(c1[i])
printf("%d %d\n",i,c1[i]);
}
return 0;
}
#include<stdio.h>
#include<string.h>
int num[111],val[111];
int c1[10000+100],c2[10000+100];
#define mod 100000007;
int main()
{
int n,i,j,k,sum;
while(scanf("%d",&n)!=EOF)
{
sum=0;
memset(num,0,sizeof(num));
for(i=1;i<=n;i++)
{
scanf("%d",&val[i]);
num[val[i]]=1;
sum+=val[i];
}
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(j=0;j<=val[1]*num[val[1]];j+=val[1])//限制了每種的個數 最多為 num[val[i]]*val[i] 由於本題都是1 可以去掉不寫
/*如 質量為1 的砝碼有4個 則母函數第一個式子為為 1+x^1+x^2+x^3+x^4*/
c1[j]=1;
for(i=2;i<=n;i++)
{
for(j=0;j<=sum;j++)//指向上一次已經計算過的式子的項
for(k=0;k+j<=sum&&k<=num[val[i]]*val[i];k+=val[i])//限制了每種的個數就要這樣寫了
{//k指向當前要成的式子的項
c2[k+j]+=c1[j]%mod;
c2[k+j]%=mod;
}
for(k=0;k<=sum;k++)
{
c1[k]=c2[k]%mod;
c2[k]=0;
}
}
for(i=1;i<=sum;i++)
if(c1[i])
printf("%d %d\n",i,c1[i]);
}
return 0;
}
下面的是官方的解題報告 ：
A.Weight
由題可知，砝碼數量不超過100，每個砝碼的重量不超過100，那麼總重不會超過10000.
我們可以申請一個數組a，a[i]表示組成重量i的數量。
那麼對於每個砝碼，我們都對a數組遍歷一遍，
當a[i]是真值時，那麼a[i+當前砝碼的重量]+=a[i](不要忘了求余)，
所以要從尾部開始遍歷，不能從頭部開始遍歷。
但是我們可以剪枝一下，每次都是從10000開始遍歷到0有點漫長。
所以我們可以定義一個數all = 0;
all存的是當前砝碼以及該砝碼之前的所有砝碼的總和重量，所以每次只要從all開始遍歷到0即可。
[cpp]
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define mod 100000007
#define N 110
#define M 10005
int a[M];
int main()
{
int n;
while (~scanf("%d", &n))
{
int all = 0;
memset(a, 0, sizeof(a));
a[0] = 1;
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
all += x;
for (int j = all; j >= 0; j--)
{
if (a[j]) a[j + x] = (a[j + x] + a[j]) % mod;
}
}
for (int i = 1; i <= all; i++)
{
if (a[i]) printf("%d %d\n", i, a[i]);
}
}
return 0;
}
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define mod 100000007
#define N 110
#define M 10005
int a[M];
int main()
{
int n;
while (~scanf("%d", &n))
{
int all = 0;
memset(a, 0, sizeof(a));
a[0] = 1;
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
all += x;
for (int j = all; j >= 0; j--)
{
if (a[j]) a[j + x] = (a[j + x] + a[j]) % mod;
}
}
for (int i = 1; i <= all; i++)
{
if (a[i]) printf("%d %d\n", i, a[i]);
}
}
return 0;
}
