kuangbin的DP习题 - I
前言
Series II开始
Sumsets - POJ - 2229
题意
求一个数字拆成2次幂所组成的数的组合种类
思路
假设这个数为i
如果i是奇数，那么dp[i] = dp[i - 1]，因为只需要在i - 1的组合种类中加一个’1’，就是i的组合种类了
如果i是偶数，那么其中一部分可通过i - 2的组合种类中加上两个’1’得到，另一部分都是偶数，那就通过i/2的组合种类中的每个元素都乘上2得到
故状态转移方程为 dp[i] = dp[i - 1](i为奇数), dp[i] = dp[i/2] + dp[i - 2](i为偶数)
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e6 + 15;
typedef long long ll;
const int MOD = 1e9;
int dp[N];
int main(){
dp[1] = 1, dp[2] = 2;
for(int i = 3; i <= N; i ++){
if(i&1) dp[i] = dp[i - 1];
else dp[i] = (dp[i - 2] + dp[i >> 1] >= MOD ? (dp[i - 2] + dp[i >> 1])%MOD : dp[i - 2] + dp[i >> 1]);
}
int n;
while(~scanf("%d", &n)){
printf("%d\n", dp[n]);
}
}
Max Sum Plus Plus - HDU - 1024
题意
选择一段序列中的m个不相交段使他们的和最大
思路
定义dp[i][j]为前i个元素并且选择第i个元素且分成j段时的最大值，则dp[i][j] = max(dp[i - 1][j], max(dp[1][j - 1], dp[2][j - 1], ..., dp[i - 1][j - 1]) + a[i]
当前选择第i个元素，则有两种情况：
第一种是把这个元素接在第 i - 1 个元素所在段的后面
第二种是自成一段，那么取dp[1][j - 1] ~ dp[i - 1][j - 1]中的最大值，这个值可以在前面的计算中得出，故使用滚动数组
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6 + 15;
const int inf = 0x7fffffff;
int a[N];
int dp[N], pre_dp[N];
int main(){
int n, m, ans;
while(~scanf("%d%d", &m, &n)){
memset(dp, 0, sizeof(dp));
memset(pre_dp, 0, sizeof(pre_dp));
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
for(int j = 1; j <= m; j++){
ans = -inf;
for(int i = j; i <= n; i++){
dp[i] = max(dp[i - 1] + a[i], pre_dp[i - 1] + a[i]);
pre_dp[i - 1] = ans;
ans = max(dp[i], ans);
}
}
printf("%d\n", ans);
}
}
Tickets - HDU - 1260
题意
排队买票时前面有n个人，每个人可买单人票，或者相邻的人可买双人票，现在给定每个人买单人票各自所需的时间，或者相邻的人买双人票所需的时间，问最早什么时候能回去（8点开始排队）
思路
状态为dp[i]，代表到第i个人时所需的最少时间，那么状态转移方程为dp[i] = min(dp[i - 1] + a[i], dp[i - 2] + b[i])，其中a为买单人票的时间数组，b为买双人票的时间数组
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e3 + 15;
int a[N], b[N], dp[N];
int main(){
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 2; i <= n; i++) scanf("%d", &b[i]);
dp[0] = 0, dp[1] = a[1];
for(int i = 2; i <= n; i++){
dp[i] = min(dp[i - 1] + a[i], dp[i - 2] + b[i]);
}
int h = dp[n]/3600;
dp[n] %= 3600;
int m = dp[n]/60;
dp[n] %= 60;
int s = dp[n];
printf("%02d:%02d:%02d am\n", h + 8, m, s);
}
}
铺地砖 HRBUST - 2186
思路
解法一：状态转移方程为dp[i] = dp[i - 2]*3 + dp[4]*2 + dp[6]*2 + ... + dp[i - 4]*2，画图可知
解法二：通过OEIS查到原来有一条递推公式 dp[i] = 4*dp[i - 1] - dp[i - 2]，可以更加高效的求解
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e3 + 15;
typedef long long ll;
ll dp[N];
int main(){
dp[0] = 1, dp[2] = 3;
for(int i = 4; i <= 45; i += 2){
dp[i] = dp[i - 2] * 3;
for(int j = 4; j <= i; j += 2){
dp[i] += dp[i - j] * 2;
}
}
int n;
while(~scanf("%d", &n)){
if(n&1) printf("%d\n", 0);
else printf("%lld\n", dp[n]);
}
}
Monkey and Banana - HDU - 1069
题意
给定n种砖，每种砖都有无限块，现在要垒砖，规定下面的砖的长和宽都必须严格大于上面的，问砖最多能垒多高
思路
LIS变形
首先输入一块砖变成六块砖，然后可列出状态转移方程 dp[i] = max(dp[1], dp[2], ..., dp[i - 1]) + a[i]，其中dp为该砖作为最下面的砖时的h最大值，最后扫描一遍dp数组找最大
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200 + 15;
const int inf = 0x7fffffff;
struct Node {
int x, y, h;
Node(int px = 0, int py = 0, int ph = 0): x(px), y(py), h(ph) {}
bool operator < (const Node& b) const{ //>
if(x != b.x) return x < b.x;
else return y < b.y;
}
};
Node a[N];
int dp[N];
int main(){
int n, csn = 0;
while(scanf("%d", &n) && n){
int tot = 0;
while(n--){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
a[++tot] = Node(x, y, z);
a[++tot] = Node(y, x, z);
a[++tot] = Node(x, z, y);
a[++tot] = Node(z, x, y);
a[++tot] = Node(y, z, x);
a[++tot] = Node(z, y, x);
}
sort(a + 1, a + tot + 1);
for(int i = 1; i <= tot; ++i){
int maxx = 0;
for(int j = 1; j < i; ++j){
if(a[j].x < a[i].x && a[j].y < a[i].y){
maxx = max(maxx, dp[j]);
}
}
dp[i] = a[i].h + maxx;
}
int ans = 0;
for(int i = 1; i <= tot; ++i){
ans = max(ans, dp[i]);
}
printf("Case %d: maximum height = %d\n", ++csn, ans);
}
}
FatMouse and Cheese - HDU - 1078
题意
从(0,0)点开始出发，每次最多向横或向纵走k步，且到达的位置中的数值必须严格大于当前位置中的数值，问数值之和最大为多少
思路
记忆化搜索（DFS + DP），与POJ滑雪那题相同
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100 + 15;
const int inf = 0x7fffffff;
int a[N][N], dp[N][N];
int dpDfs(int x, int y, int n, int k){
if(dp[x][y]) return dp[x][y];
int maxx = 0;
for(int i = x - k; i <= x + k; i++){
if(i < 1 || i > n) continue;
if(a[i][y] <= a[x][y]) continue;
maxx = max(maxx, dpDfs(i, y, n, k));
}
for(int j = y - k; j <= y + k; j++){
if(j < 1 || j > n) continue;
if(a[x][j] <= a[x][y]) continue;
maxx = max(maxx, dpDfs(x, j, n, k));
}
dp[x][y] = a[x][y] + maxx;
return a[x][y] + maxx;
}
int main(){
int n, k;
while(scanf("%d%d", &n, &k) && n != -1 && k != -1){
memset(dp[0], 0, sizeof(dp));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &a[i][j]);
}
}
printf("%d\n", dpDfs(1, 1, n, k));
}
}
Phalanx HDU - 2859
题意
求矩阵中对称子矩阵阶数最大值
思路
定义dp为当前点作为左下角点所在矩阵阶数最大值，则dp[i][j] = dp[i - 1][j + 1] + 1 或 dp[i][j] = 1，除了获取右上角dp值外，还要往上扫描和往右扫描看对应元素是否相同，相同则+1，不同则为1
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000 + 15;
const int inf = 0x7fffffff;
char a[N][N];
int dp[N][N];
int main(){
int n;
while(scanf("%d", &n) && n){
for(int i = 1; i <= n; ++i){
getchar();
for(int j = 1; j <= n; ++j){
a[i][j] = getchar();
}
}
int ans = 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
dp[i][j] = 1;
if(i == 1 || j == n) continue;
int maxk = dp[i - 1][j + 1];
int maxx = 1;
while(maxx <= maxk && a[i][j + maxx] == a[i - maxx][j]) ++maxx;
dp[i][j] = maxx;
ans = max(ans, maxx);
}
}
printf("%d\n", ans);
}
}
