背包问题

货币拼凑问题

P5020 [NOIP2018 提高组] 货币系统
考虑大面值的货币若能被小面值的货币凑出，那么这个大面值货币就一定是多余的
将货币大小又小到大排序，从大面值的货币一直枚举到小的货币，再嵌套枚举一层比当前货币面值小的货币，利用完全背包思想判断大面值的货币能否被小面值的货币所表示，若能，必要货币数量减去 11 即可

1
2
3
4
5
6
7
8
9
10
11
12
void Solve(){
	int ans = n;
	sort(a + 1, a + 1 + n);
	for(int i = n; i >= 1; i --){
		memset(f, 0 ,sizeof(f));
		for(int o = 1; o < i; o ++)
			for(int j = a[o]; j <= a[i]; j ++)
				f[j] = max(f[j], f[j - a[o]] + a[o]);
		if(f[a[i]] == a[i]) ans --;
	}
	printf("%d\n", ans);
}

其实这种问题最快的方法是筛法，即将从 11 到最大货币面值枚举货币面值，若该货币面值可以被表示，则枚举所有的货币，依次加上，将这种方式表示成功的面值进行标记，最后统计未被标记的即可
时间复杂度为 O(max(ai)n)O(max(a_i)n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
memset(f, 0, sizeof(f));
		memset(a, 0, sizeof(a));
		scanf("%d", &n);
		for(int i = 1; i <= n; i ++){
			scanf("%d", &a[i]);
			f[a[i]] = 2;
		} 
		sort(a + 1, a + 1 + n);
		for(int i = 1; i <= a[n]; i ++){
			if(!f[i]) continue;
			for(int j = 1; j <= n; j ++)
				if(i + a[j] <= a[n]) f[i + a[j]] = 1;
				else break;
		}
		int ans = 0;
		for(int i = 1; i <= a[n]; i ++) if(f[i] == 2) ans ++;
		printf("%d\n", ans);

区间 DP

涂色问题

P4170 [CQOI2007]涂色
这类问题只需要在朴素区间 DP 过程中加上端点相同颜色转移方程，即当区间左右端点相同时，本就可以在之前就一次性涂过，枚举断点前判断即可

1
2
3
4
5
6
7
for(int len = 2; len <= n; len ++)
		for(int l = 1; l + len - 1 <= n; l ++){
			int r = l + len - 1;
			if(a[l] == a[r]) f[l][r] = min(f[l + 1][r], f[l][r - 1]);
			for(int k = l; k <= r; k ++)
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
		}