数字组合

本题，很明显可以看出N是n个物品，M为背包容积，由于题目要求的是和为j是的方案数，所以我们很容易得出状态转移方程：f[j] += f[j-a[i]];

1
2
3
4
5
6
7
8
9
10
11
void solve() {
    cin>>n>>m;
    rep(i,1,n)  cin>>a[i];
    f[0]=1;
    rep(i,1,n){
        fep(j,m,a[i]){
            f[j]+=f[j-a[i]];
        }
    }
    cout<<f[m]<<'\n';
}

自然数拆分Lunatic版

完全背包

1
2
3
4
5
6
7
8
9
10
void solve() {
    cin>>n;
    f[0]=1;
    rep(i,1,n){
        rep(j,i,n){
            f[j]=(f[j]+f[j-i])%mod;
        }
    }
    cout<<f[n]-1<<'\n';
}

Jury Compromise

Jury Compromise

题面翻译

在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。陪审团是由法官从公民中挑选的。

法官先随机挑选 \(N\) 个人（编号 \(1,2…,N\)）作为陪审团的候选人，然后再从这 \(N\) 个人中按照下列方法选出 \(M\) 人组成陪审团。

首先，参与诉讼的控方和辩方会给所有候选人打分，分值在 \(0\) 到 \(20\) 之间，第 \(i\) 个人的得分分别记为 \(p_i\) 和 \(d_i\)。

为了公平起见，法官选出的 \(M\) 个人必须满足：辩方总分 \(D\) 和控方总分 \(P\) 的差的绝对值 \(|D-P|\) 最小。

如果选择方法不唯一，那么再从中选择辨控双方总分之和 \(D+P\) 最大的方案。

求最终的陪审团获得的辩方总分 \(D\)、控方总分 \(P\)，以及陪审团人选的编号。

注意：若陪审团的人选方案不唯一，则任意输出一组合法方案即可。

感谢 @fleetingtime @君临征天下 提供的翻译

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

1
2
3
4
5
6
4 2
1 2
2 3
4 1
6 2
0 0

样例输出 #1

1
2
3
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
 2 3

可以考虑f[i] [j] [k]表示前i个人选了j个人并且差值为k的和最大的方案

那么状态该如何转移呢?

考虑第i个人选或不选

若不选第i个人

(f[i][j][k] == f[i - 1][j][k])

选了就是

f[i][j][k]=max(f[i-1][j-1][t]+p[i]+d[i],f[i][j][k]);

t=k-p[i]+d[i];

然后就是输出方案

判断是否相等

如果相等说明可以不选

不相等就一定选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, a, n) for (ll i = a; i <= n; i++)
#define frep(i, a, n) for (ll i = a; i >= n;i--)
int f[205][25][805];
int p[205];
int d[205];
int tot;
void output(int i,int j,int k)//输出方案
{
    int ans[25], cnt = 0, P = 0, D = 0;
    while(j)
    {   
        if(f[i][j][k] == f[i - 1][j][k])
            i--;
        else 
        {
            ans[++cnt] = i;
            k -= (p[i] - d[i]);
            P += p[i];
            D += d[i];
            j--, i--;
        }
    }
    printf("Jury #%d\n", ++tot);
    printf("Best jury has value %d for prosecution and value %d for defence:\n", P, D);
   frep(u,cnt,1)
   {
    cout<<" "<<ans[u];   
   }
    cout<<'\n'<<'\n';//注意要多输出一个换行
}

int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0)
{
    break;
}
  for (int i = 1; i <= n;i++)
           cin>>p[i]>>d[i];
memset(f,-0x3f,sizeof f);
f[0][0][400]=0;
//400是边界线
rep(i,1,n)
{
    rep(j,0,m)
    {
        rep(k,0,800)
        {
            f[i][j][k]=f[i-1][j][k];
            if(j<1)
            {
                continue;
            }
            int t=k-p[i]+d[i];
            if(t<0||t>800)
            {
            continue;
            }
            f[i][j][k]=max(f[i-1][j-1][t]+p[i]+d[i],f[i][j][k]);
        }
    }
}
rep(i,0,400)
{
if(f[n][m][400-i]>=0||f[n][m][400+i]>=0){
    if(f[n][m][400-i]>f[n][m][400+i])
    {
        output(n,m,400-i);
        break;
    }
    else
    {
        output(n,m,400+i);
        break;
    }

}
}
}
return 0;
}

Coins

给出硬币面额及每种硬币的个数，求从1到m能凑出面额的个数

二进制优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,m,a[N],c[N];
int w[N];
bool f[N];
int main() {
	cin>>n>>m;
	while(n && m) 
    {
		memset(f,0,sizeof(f)); int ans=0;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>c[i];
		int cnt=0;
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=c[i];j<<=1) 
                w[++cnt]=j*a[i],c[i]-=j;
			if(c[i]) w[++cnt]=c[i]*a[i];
		} f[0]=1;
		for(int i=1;i<=cnt;i++) 
		for(int j=m;j>=w[i];j--)
				f[j]|=f[j-w[i]];
		for(int i=1;i<=m;i++) ans+=f[i];
		cout<<ans<<'\n';		
		cin>>n>>m;
	}
	return 0;
}