简单DP
背包问题
G - 免费馅饼
HDU - 1176
题意
小明初始站在长度为10的数轴上5的位置。每秒钟会从天上掉下馅饼，给出掉落的位置x和时间T，求最大能接到的馅饼数。
题解
基础DP。
下一秒这个位置最大能接到的馅饼数是上一秒这个位置以及左、右位置馅饼数的最大值，递推即可。
代码
#include <algorithm>
#include <cstring>
using namespace std ;
int a[100001][12];
int f[100001][12];
int main (){
int n;
while (scanf("%d", &n) != EOF && n) {
memset (a, 0, sizeof a) ;
memset (f, 0, sizeof f) ;
int x, T, i, j, maxT = 0 , ans = 0 ;
while (n--) {
scanf ("%d%d", &x, &T);
++a[T][x];
maxT = max(maxT, T);
}
f[1][4] = a[1][4];
f[1][5] = a[1][5];
f[1][6] = a[1][6];
for (i = 2; i <= maxT; ++i){
for ( j = 0; j < 11; ++j) {
f[i][j] = f[i-1][j];
if (j > 0)
f[i][j] = max(f[i][j], f[i-1][j-1]);
if (j < 10)
f[i][j] = max(f[i][j], f[i-1][j+1]);
f[i][j] += a[i][j];
}
}
for (i = 0; i < 11; ++i)
ans = max(ans, f[maxT][i]);
printf("%d\n", ans);
}
return 0;
}
E - Super Jumping! Jumping! Jumping!
HDU - 1087
题意
给出一个一维棋盘，最左起点最右终点，每个位置都有一个整数值，可以从值小的位置向右跳到值大的位置。得分是路径上值的总和。求最大得分。
题解
基础DP。
下一个点的最大得分是前面所有点中的最大得分点加上它自己的值。
代码
#include <stdio.h>
#include <string.h>
int main(){
int n, v[1005], dp[1005];
while (scanf("%d", &n), n) {
memset(dp, 0, sizeof(dp));
int maxn = 0;
for (int i = 1; i <= n; ++i)
scanf("%d", v+i);
for (int i = 1; i <= n; ++i){
int max = 0;
for (int j = 1; j < i; ++j){
if (dp[j] > max && v[j] < v[i])
max = dp[j];
}
dp[i] = max + v[i];
maxn = maxn<dp[i]? dp[i]: maxn;
}
printf("%d\n", maxn);
}
return 0;
}
J - FatMouse's Speed
HDU - 1160
题意
给出一群老鼠的体重和奔跑速度，求一个最长的老鼠编号序列，这个序列中的老鼠体重递增，奔跑速度递减。
题解
最长上升（下降）子序列。
先按照体重排个序，然后最长下降子序列DP即可。
WA了好几次，主要是对这个算法还不是很了解，应该是O(nlogn)的时间复杂度。
输出序列用到了前驱数组和递归输出。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct mouse{
int w, s, id;
}mice[1005];
bool cmp(mouse a, mouse b){
if (a.w == b.w)
return a.s > b.s;
return a.w < b.w;
}
void output(int cur, int pre[]){
if (cur == 0) return;
output(pre[cur], pre);
printf("%d\n", mice[cur].id);
}
int main(){
int t = 1;
mice[0].w = 0, mice[0].s = 10005;
while (~scanf("%d%d", &mice[t].w, &mice[t].s)){
mice[t].id = t;
++t;
}
sort(mice+1, mice+t, cmp);
int dp[1005] = {0}, maxn = 1, pre[1005] = {0}, cur = 1;
for (int i = 1; i < t; ++i){
for (int j = 0; j < i; ++j){
if (mice[j].w < mice[i].w && mice[j].s > mice[i].s && dp[j]+1 > dp[i]){
dp[i] = dp[j]+1;
pre[i] = j;
if (dp[i] > maxn){ maxn = dp[i]; cur = i; }
}
}
}
printf("%d\n", maxn);
output(cur, pre);
return 0;
}
L - Common Subsequence
POJ - 1458
题意
给出两个字符串，求它们的最长公共子序列长度。
题解
最长公共子序列，裸题。
if (a[i] == b[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
char a[1005], b[1005];
while (~scanf("%s%s", a+1, b+1)){
int dp[1005][1005] = {0};
int x = strlen(a+1), y = strlen(b+1);
for (int i = 1; i <= (int)strlen(a+1); ++i){
for (int j = 1; j <= (int)strlen(b+1); ++j){
if (a[i] == b[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
printf("%d\n", dp[x][y]);
}
return 0;
}
M - Help Jimmy
POJ - 1661
题意
Jimmy从坐标为(x,y)的点掉落下来，速度1单位/s，如果掉落下去的距离超过了max就会摔死。空间中有许多横着的木板，属性为(x1,x2,h)。在木板上可以横向移动，速度1单位/s。求最快到达地面的时间。
题解
基础DP。
用dp[i][0]表示从第i块木板左侧掉落的到达地面时间，dp[i][1]表示右侧。转移方程为：
dp[i][0] =
p[i].h - p[k].h +
min(dp[k][0]+p[i].x1-p[k].x1,
dp[k][1]+p[k].x2-p[i].x1);
dp[i][1] =
p[i].h - p[k].h +
min(dp[k][0]+p[i].x2-p[k].x1,
dp[k][1]+p[k].x2-p[i].x2);
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
struct plat{
int x1, x2, h;
}p[1005];
int maxn, dp[1005][2];
bool cmp(plat a, plat b){
return a.h < b.h;
}
void calc_left(int i){
int k = i - 1;
while (k > 0 && p[i].h - p[k].h <= maxn){
if (p[i].x1 >= p[k].x1 && p[i].x1 <= p[k].x2){
dp[i][0] = p[i].h - p[k].h + min(dp[k][0]+p[i].x1-p[k].x1,
dp[k][1]+p[k].x2-p[i].x1);
return;
} else --k;
}
if (p[i].h - p[k].h > maxn)
dp[i][0] = 0x3f3f3f3f;
else
dp[i][0] = p[i].h;
}
void calc_right(int i){
int k = i - 1;
while (k > 0 && p[i].h - p[k].h <= maxn){
if (p[i].x2 >= p[k].x1 && p[i].x2 <= p[k].x2){
dp[i][1] = p[i].h - p[k].h + min(dp[k][0]+p[i].x2-p[k].x1,
dp[k][1]+p[k].x2-p[i].x2);
return;
} else --k;
}
if (p[i].h - p[k].h > maxn)
dp[i][1] = 0x3f3f3f3f;
else
dp[i][1] = p[i].h;
}
void solve(){
memset(dp, 0, sizeof dp);
int n;
scanf("%d%d%d%d", &n, &p[0].x1, &p[0].h, &maxn);
++n, p[0].x2 = p[0].x1;
for (int i = 1; i < n; ++i)
scanf("%d%d%d", &p[i].x1, &p[i].x2, &p[i].h);
p[n].x1 = -20001, p[n].x2 = 20001, p[n].h = 0;
sort(p, p+n+1, cmp);
for (int i = 1; i <= n; ++i){
calc_left(i);
calc_right(i);
}
printf("%d\n", min(dp[n][0], dp[n][1]));
}
int main(){
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}
状态压缩DP
D - Doing Homework
HDU - 1074
题意
给出n门作业的名称、截止时间和所需时间。当超过截止时间时会扣分。求最小的扣分数和做作业的顺序。
题解
状态压缩DP。
看了题解才知道这样做。
首先是二进制法遍历集合全排列，然后遍历当前排列中包含的上一个做完的作业，即遍历每一种作业，找出扣分的最小值作为上一个做完的作业。记录这一状态，并且记录前驱（输出用）。
代码
/******************************
*File name: hdu1029.cpp
*Author: wzhzzmzzy
*Created Time: 日 4/23 20:01:35 2017
*TODO: HDU 1029 状压DP 水
******************************/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
char name[16][200];
int t[1<<15], deadline[16], finish[16];
int pre[1<<15], dp[1<<15];
void output(int m){
if (!m) return;
output(m-(1<<pre[m]));
printf("%s\n", name[pre[m]]);
}
int main(){
int T;
scanf("%d", &T);
while (T--){
int n;
scanf("%d", &n);
int maxn = 1<<n;
for (int i = 0; i < n; ++i)
scanf("%s%d%d", name[i], deadline+i, finish+i);
for (int i = 1; i < maxn; ++i){
dp[i] = 0x3f3f3f3f;
for (int j = n-1; j >= 0; --j){
int te = 1<<j;
if (!(i&te)) continue;
int score = t[i-te]-deadline[j]+finish[j];
if (score < 0) score = 0;
if (dp[i] > dp[i-te]+score){
dp[i] = dp[i-te]+score;
t[i] = t[i-te]+finish[j];
pre[i] = j;
}
}
}
printf("%d\n", dp[maxn-1]);
output(maxn-1);
}
return 0;
}
数位DP
不要62
HDU - 2089
题意
求从l到r的所有数字中，不含有4和62的数字有多少。
题解
数位DP入门。
用dp[i][j]表示j开头的i位数。首先打表，然后根据读入的数字挨个匹配累加即可。
递推公式：
for (int i = 1; i < 7; ++i)
for (int j = 0; j < 10; ++j)
for (int k = 0; k < 10; ++k)
if (j != 4 && !(j == 6 && k == 2))
dp[i][j] += dp[i-1][k];
代码
/******************************
*File name: hdu2089.cpp
*Author: wzhzzmzzy
*Created Time: 二 4/25 20:05:44 2017
*TODO: HDU 2089 数位DP
******************************/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
int dp[8][10];
void init(){
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (int i = 1; i < 7; ++i)
for (int j = 0; j < 10; ++j)
for (int k = 0; k < 10; ++k)
if (j != 4 && !(j == 6 && k == 2))
dp[i][j] += dp[i-1][k];
}
int calc(int x){
int digit[8], len = 0, ans = 0;
while (x > 0){
digit[++len] = x%10;
x /= 10;
}
digit[len+1] = 0;
for (int i = len; i; --i){
for (int j = 0; j < digit[i]; ++j)
if (j != 4 && !(digit[i+1]==6&&j==2))
ans += dp[i][j];
if (digit[i] == 4||(digit[i]==2&&digit[i+1]==6))
break;
}
return ans;
}
int main(){
int n, m;
init();
while (~scanf("%d%d", &n, &m) && n && m){
printf("%d\n", calc(m+1)-calc(n));
}
}
