2019.7.13
集训dp基础题
POJ 3176 Cow Bowling
给你一个三角形，从第一个往下选，每次只能选该数下面的两个最近的数中的一个，问能取的数的最大总和。
题解：
dp[i] [j] = max(dp[i-1] [j-1], dp[i] [j]) + a[j];(j != 0 && j != i)
dp[i] [0] = dp[i-1] [0] + a[0];
dp[i] [j] = dp[i-1] [j-1] + a[i]; (i == j)
最后枚举dp[n-1] [j] (0 <= j < n)求最大就是了。
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int n;
while(~scanf("%d", &n)) {
int dp[360][360], maxn = 0, a;
for(int i = 0; i < n; i++) {
for(int j = 0; j <= i; j++) {
scanf("%d", &a);
if(i == 0 && j == 0) dp[i][j] = a;
else if(j == 0) dp[i][j] = dp[i-1][j] + a;
else if(j == i) dp[i][j] = dp[i-1][j-1] + a;
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a;
}
}
for(int i = 0; i < n; i++) {
if(maxn < dp[n-1][i]) maxn = dp[n-1][i];
}
printf("%d
", maxn);
}
return 0;
}
POJ 2229 Sumsets
输入一个n，把n拆分成2的次方相加，问方案数。
题解：
dp[1] = 1;
dp[i] = dp[i-1] + dp[i/2] ;(i 是偶数)
dp[i] = dp[i-1];(i是奇数)
/*
2 = 1+1;
2 = 2;
//显然3可以直接从2推出，奇数都可以
3 = 1+1+1;
3 = 2+1;
//4的前两个可以由3直接推出，而后两个除以2恰好可以由2推出
4 = 1+1+1+1;
4 = 2+1+1;
4 = 2+2;
4 = 4;
*/
#include <cstdio>
int dp[1000010];
int mod = 1e9;
int main() {
int n;
dp[1] = 1, dp[2] = 2;
for(int i = 3; i < 1000010; i++) {
dp[i] = dp[i-1] % mod;
if(i % 2 == 0) dp[i] = (dp[i] + dp[i/2]) % mod;
}
while(~scanf("%d", &n)) {
printf("%d
", dp[n]);
}
return 0;
}
POJ 2385 Apple Catching
有两棵苹果树会掉苹果，T秒内每秒会在某一棵苹果树掉苹果，但是John很懒，只愿意移动至多w次，问他能接到的最多苹果树。（刚开始他在1号树
题解：
如果是偶数次移动，那么他肯定在1号树，如果是奇数次移动，他就会在2号树；
dp[i] [j] 第i秒移动j次的最多苹果数。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
int n, k;
while(~scanf("%d %d", &n, &k)) {
int dp[3010][35], a[3010];
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i]--;
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= k; j++) {
if(j % 2) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i];
else {
if(j) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + !a[i];
else dp[i][j] = dp[i-1][j] + !a[i];
}
}
}
printf("%d
", dp[n][k]);
}
return 0;
}
POJ 3616 Milking Time
给出多个开始时间和结束时间及该段时间能挤的牛奶的量，每次工作相隔k小时，比如你4结束工作，那么最早能在k+4开始新一轮工作，求你能挤的牛奶的量最多是多少。
题解：按结束时间从小到大排序；
dp[i] 表示第i个小时能挤的最多的牛奶的量
dp[i] = max(max(dp[i], dp[i-a[cnt].u] + a[cnt].w), w[i])
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int u, v, w;
}a[1000010];
int dp[1000010];
bool cmp(node x, node y) {
return x.v < y.v;
}
int main(){
int n, m, k;
while(~scanf("%d %d %d", &n, &m, &k)) {
for(int i = 0; i < m; i++) {
scanf("%d %d %d", &a[i].u, &a[i].v, &a[i].w);
}
sort(a, a + m, cmp);
memset(dp, 0, sizeof(dp));
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(i == a[cnt].v) {
while(i == a[cnt].v) {
dp[i] = max(max(dp[i],dp[i-1]), a[cnt].w);
if(a[cnt].u >= k) dp[i] = max(dp[i] , dp[a[cnt].u - k] + a[cnt].w);
cnt++;
}
}
else dp[i] = dp[i-1];
}
printf("%d
", dp[n]);
}
return 0;
}
POJ 3280 Cheapest Palindrome
给你一个字符串，通过删减或者插入一些字母，使得这个字符串成为回文字符串，每一个字母都有删减和插入该字母的体力值a[i]和b[i]，求体力值最少
题解：
在字符串中，插入一个字母和删减一个字母的效果是一样的，c[i] = min(a[i], b[i])；
dp[i] [j] 表示第i位到第j位最少体力值。
dp[i] [j] = min(dp[i-1] [j] + c[i], dp[i] [j-1] + c[j)；（str[i] !+ str[j])
dp[i] [j] = dp[i+1] [j-1];(str[i] == str[j])
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
const int maxm = 2005;
char ch[2];
int change[27];
char str[maxm];
int dp[maxm][maxm];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
scanf("%s",str);
int add,del;
for(int i = 0;i < n;i++){
scanf("%s %d %d",ch,&add,&del);
int pos = ch[0] - 'a';
change[pos] = min(add,del);
}
for(int i = m - 1;i >= 0;i--){
for(int j = i + 1;j < m;j++){
dp[i][j] = min(dp[i][j - 1] + change[str[j] - 'a'],dp[i + 1][j] + change[str[i] - 'a']);
if(str[i] == str[j])
dp[i][j] = min(dp[i][j],dp[i + 1][j - 1]);
}
}
printf("%d
",dp[0][m - 1]);
return 0;
}
POJ 1742 Coins
题意：给你n种银币，每种硬币价值为a[i], 有c[i]个，问这些银币能组成1-m之间多少个数
题解：看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
int n, m;
while(~scanf("%d %d", &n, &m) && n + m) {
int a[110], b[110],dp[100010], ans = 0;
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n; i++) scanf("%d", &b[i]);
for(int i = 0; i < n; i++) {
for(int j = 0; j <= m; j++) {
if(dp[j] > 0) dp[j] = b[i] + 1;
//如果前面能组成j的面值，那么dp[j]最多能再放b[i]种个a[i]面值的银币
//因为dp[i] = 0表示不能组成i面值，所以dp[j] = b[i]+1;表示在dp[j]>0的时候，再放b[i]个a[i]的银币的情况是存在的
}
for(int j = 0; j <= m - a[i]; j++) {
if(dp[j] > 0) dp[j+a[i]] = max(dp[j+a[i]], dp[j] - 1);
//如果dp[j]存在,那么加入一个a[i]的银币后能最多再放多少个a[i]的银币
}
}
for(int i = 1; i <= m; i++) {
if(dp[i]) ans++;
}
printf("%d
", ans);
}
return 0;
}
POJ 3046 Ant Counting
有n个蚂蚁，属于1-t个家族，问从这些蚂蚁里面取出A, A+1...B个蚂蚁，一共有多少种取法？
题解：挑战书68-69页
状态转移方程：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1] - dp[i-1] [j - 1 - a[i - 1]];
#include <cstdio>
#include <cstring>
int dp[1010][100010];
int main() {
int t, n, A, B;
while(~scanf("%d %d %d %d", &t, &n, &A, &B)) {
int b, a[1010], ans = 0;
memset(a, 0, sizeof(a));
for(int i = 0; i < n; i++) {
scanf("%d", &b);
a[b-1]++;
}
for(int j = 0; j <= t; j++) {
dp[j][0] = 1;
}
for(int j = 1; j <= t; j++) {
for(int k = 1; k <= B; k++) {
if(k - 1 - a[j - 1] >= 0) {
dp[j][k] = (dp[j-1][k] + dp[j][k-1] - dp[j-1][k - 1- a[j-1]] + 1000000) % 1000000;
}
else {
dp[j][k] = (dp[j-1][k] + dp[j][k-1]) % 1000000;
}
}
}
for(int i = A; i <= B; i++) {
ans = ans % 1000000 + dp[t][i];
}
printf("%d
", ans%1000000);
}
return 0;
}
POJ 3181 Dollar Day
题意：有价值为1-m的银币，每种银币有无数个，问用这些银币组成n有多少种？
题解：dp[i] [j] 表示组成价值为i且最大的银币的值不超过j的方法
dp[i] [j] = dp[i] [j -1] + dp[i-j] [j];
注意此处需要高精度，下面方法很巧妙
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long a[1005][105],b[1005][105],inf = 1e18;
int main()
{
int n, m;
while(~scanf("%d %d",&n,&m))
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i = 0;i <= m;i++) a[0][i] = 1;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(i<j)
{
a[i][j] = a[i][j-1];
b[i][j] = b[i][j-1];
continue;
}
b[i][j] = b[i-j][j]+b[i][j-1]+(a[i-j][j]+a[i][j-1])/inf;
a[i][j] = (a[i-j][j]+a[i][j-1])%inf;
}
}
if(b[n][m]) printf("%I64d",b[n][m]);
printf("%I64d
",a[n][m]);
}
return 0;
}
CF 1133E K Balanced Teams
有n个学生，每个学生都有自己的智力值，他们最多组成k个组合，但是一个组合内的学生智力值不能超过5，问最多有多少学生能组成组合？
题解：dp[i] [j] 表示前i个学生组成j个组合的最多人数
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[5010][5010],a[5010];
int main(){
int n,k;
scanf("%d %d",&n,&k);
for(int i = 1;i <=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
int j=i;
while(j>1&&a[i]-a[j-1]<=5) j--;
for(int t = 1;t<=k;t++)
dp[i][t]=max(dp[i-1][t],dp[j-1][t-1]+i-j+1);
}
printf("%d
",dp[n][k]);
return 0;
}