Algorithm2.7 线性dp
[TOC]
线性dp
时间线问题
https://www.luogu.com.cn/problem/P1095
题目大意：时间线上，每秒钟 => 可以选择a方式，属性c变化1；可以选择b方式，属性c变化2。
1、dp[i]表示在时间为i的时候，最远可到达的距离。
2、预处理：由于已知了a方式更好，那么可以优先通过a方式对数据dp进行预处理
3、状态转移方程：dp[i] = max(dp[i], dp[i-1]+17)
#include <iostream>
using namespace std;
#define maxn 300010
int m, s, t, dp[maxn];
int main() {
scanf("%d%d%d", &m, &s, &t);
// 预处理
for (int i = 1; i <= t; ++i)
if (m >= 10) {m-=10;dp[i] = dp[i-1]+60;}
else {m+=4;dp[i] = dp[i-1];}
// 状态转移
for (int i = 1; i <= t; ++i) dp[i] = max(dp[i], dp[i-1]+17);
if (dp[t] >= s) {
printf("Yes\n");
for (int i = 1; i <= t; ++i) if (dp[i] >= s) {printf("%d\n", i);break;}
} else printf("No\n%d", dp[t]);
return 0;
}
https://www.luogu.com.cn/problem/P1280
题目大意：
#include <iostream>
using namespace std;
#define maxn 10010
struct node{
int bg, l;
bool operator < (const node n) const{
return bg > n.bg;
}
}a[maxn];
int n, k, dp[maxn], bt[maxn], idx = 0; // dp[i]表示i-n的最大空闲时间, bt[i]代表第i时刻为开始时刻的工作数量
// 初始化：
// 状态转移方程：当没有任务的时候：dp[i] = dp[i+1]+1;当有任务的时候，就要斟酌是否做这个任务(max(做，不做))，dp[i] = max(dp[i], dp[i+a[j].l]);
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < k; ++i) {scanf("%d%d", &a[i].bg, &a[i].l);bt[a[i].bg]++;}
sort(a, a+n);
for (int i = n; i >= 1; --i) {
if (!bt[i]) dp[i] = dp[i+1]+1;
else
for (int j = 0; j < bt[i]; ++j) {
// 遍历当前时间点开始的所有任务
dp[i] = max(dp[i], dp[i+a[idx].l]);
idx++;
}
}
printf("%d\n", dp[1]);
// for (int i = 1; i <= n; ++i) printf("%d -- %d\n", i, dp[i]);
return 0;
}
#include <iostream>
using namespace std;
#define maxn 10010
typedef long long ll;
struct node{
ll bg, l;
bool operator < (const node n) const{
return bg > n.bg;
}
}a[maxn];
ll n, k, dp[maxn], bt[maxn], idx = 0;
#include <algorithm>
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < k; ++i) {scanf("%lld%lld", &a[i].bg, &a[i].l);bt[a[i].bg]++;}
sort(a, a+k);
for (int i = n; i >= 1; --i)
if (!bt[i]) dp[i] = dp[i+1]+1;
else for (int j = 0; j < bt[i]; ++j) dp[i] = max(dp[i], dp[i+a[idx++].l]);
printf("%lld\n", dp[1]);
return 0;
}
LCS O(n^2)
https://www.luogu.com.cn/problem/P1439
题目大意：
#include <iostream>
using namespace std;
#define maxn 100010
int n, a[maxn], b[maxn], dp[maxn][maxn]; //dp[i][j] i是在第一个串中的索引的位置，j是第二个串中的索引的位置
// 初始化：
// 状态转移方程：dp[i][j] = a[i] == a[j] ? dp[i-1][j-1]:max(dp[i-1][j], dp[i][j-1]);
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = (a[i] == b[j] ? dp[i-1][j-1]+1:max(dp[i-1][j], dp[i][j-1]));
printf("%d\n", dp[n][n]);
return 0;
}
LCS的O(nlogn)优化
LIS O(n^2)
#include <iostream>
using namespace std;
#define maxn 10010
int n, a[maxn], dp[maxn], ans; // dp[i]表示到i之前的最长递增序列
// 初始化：
// 状态转移方程：dp[j] = max
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j)
if (a[i] > a[j]) dp[i] = max(dp[i], dp[j]+1);
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
return 0;
}