DP入门题
PATA1007
题目要求求出最大子序列的各元素之和，并且输出最大子序列的第一个元素和最后一个元素的值。使用一个dp数组，dp[i]表示以第i个元素为末尾的和最大的序列。由于需要用到序列的首元素，所以在DP时就要记录。状态转移方程如下：
\(dp[0].start=0;dp[0].v=dat[0]\)
\(dp[i-1]<0,dp[i].start=i,dp[i].v=dat[i]\)
\(dp[i-1]\geq 0,dp[i].start=dp[i-1].start,dp[i].v=dat[i]+dp[i-1].v\)
题目要求要求按照一定的优先级输出结果，即最大值、i、j，那么可以使用三轮遍历，也可以自定义一个比较函数使用sort(时间复杂度会增加)。
代码如下：
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 10010;
int K = 0;
struct node {
int start, end, v;
node(int a,int b,int c):start(a),end(b),v(c){}
node(){}
};
//dp数组,第i个元素储存以i为末尾的序列的最大值
struct node dp[MAX];
//原始data
int dat[MAX] = { 0 };
//全为负数？
bool flag = true;
void input() {
cin >> K;
for (int i = 0; i < K; i++) {
cin >> dat[i];
if (dat[i] >= 0) flag = false;
}
}
struct cmp {
bool operator()(const struct node& a, const struct node& b) {
if (a.v != b.v) return a.v > b.v;
if (a.start != b.start) return a.start < b.start;
if (a.end != b.end) return a.end < b.end;
}
};
int main(void) {
ios::sync_with_stdio(false);
input();
if (flag) {
cout << 0 << " " << dat[0] << " " << dat[K - 1] << endl;
return 0;
}
//dp计算
dp[0] = node(0, 0, dat[0]);
for (int i = 1; i < K; i++) {
int s, v;
if (dp[i - 1].v >= 0) {
s = dp[i - 1].start;
v = dp[i - 1].v + dat[i];
}
else {
s = i;
v = dat[i];
}
dp[i] = node(s, i, v);
}
//输出结果
//将结果排序
sort(dp, dp + K, cmp());
cout << dp[0].v <<" "<< dat[dp[0].start] <<" "<< dat[dp[0].end]< patA1045之LIS做法
使用最长不下降子序列做法，dp[i]储存以第i个元素结尾的所有序列的最大长度，可以写出状态转移方程：
\(dp[i]=MAX\{1,dp[j]+1\},j\in \{0...i-1\} \and j的顺序先于i\)
关键在于如何表示顺序的先后关系。代码1的思路是使用一个二维数组，[i][j]的意义即为数字j允许出现在数字i之前。但这样代码较为冗长。
代码1
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 10010;
const int MAX2 = 205;
int N, M, L;
//newl储存去掉所有不喜欢的颜色后的色带元素个数
int newl;
//map[i][j]表示j可以出现在i之前
bool map1[MAX2][MAX2] = { false };
//储存去掉不喜欢颜色后的色带
vector dat;
//储存喜欢的颜色
vector color;
set colorset;
void input() {
cin >> N;
cin >> M;
for (int i = 0; i < M; i++) {
int c; cin >> c; color.push_back(c); colorset.insert(c);
}
cin >> L;
for (int i = 0; i < L; i++) {
int c; cin >> c;
if (colorset.find(c) != colorset.end()) {
dat.push_back(c);
}
}
}
//创建映射
void createmap() {
for (int i = 0; i < color.size(); i++) {
int key = color[i];
for (int j = 0; j <= i; j++) {
map1[key][color[j]] = true;
}
}
}
int dp[MAX] = { 0 };
int main(void) {
ios::sync_with_stdio(false);
input();
createmap();
//dp求解,dp[i]储存以色带第i个元素为末尾且满足顺序的所有序列中，序列的最大长度
dp[0] = 1;
for (int i = 1; i < dat.size(); i++) {
int dpmax = 0;
for (int j = 0; j < i; j++) {
//元素j的顺序在i之前
if (map1[dat[i]][dat[j]]) {
if (dp[j] > dpmax) dpmax = dp[j];
}
}
dp[i] = (dpmax == 0 ? 1 : dpmax+1);
}
int result=*max_element(dp,dp+dat.size());
cout << result << endl;
}
代码2借鉴了教材。使用一个数组来完成数字到顺序间的映射关系。然后在dp时直接按照映射得到相对的顺序。
代码如下：
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 10010;
const int MAX2 = 205;
int N, M, L;
//储存去掉不喜欢颜色后的色带
vector dat;
//映射，将喜欢的颜色映射到0,1,2...
int myhash[MAX2];
void input() {
cin >> N;
cin >> M;
for (int i = 0; i < M; i++) {
int c; cin >> c;
myhash[c] = i;
}
cin >> L;
for (int i = 0; i < L; i++) {
int c; cin >> c;
if (myhash[c]!=-1) {
dat.push_back(c);
}
}
}
int dp[MAX] = { 0 };
int main(void) {
fill(myhash, myhash + MAX2, -1);
ios::sync_with_stdio(false);
input();
//dp求解,dp[i]储存以色带第i个元素为末尾且满足顺序的所有序列中，序列的最大长度
dp[0] = 1;
for (int i = 1; i < dat.size(); i++) {
int dpmax = 0;
for (int j = 0; j < i; j++) {
//元素j的顺序在i之前
if (myhash[dat[i]]>=myhash[dat[j]]) {
if (dp[j] > dpmax) dpmax = dp[j];
}
}
dp[i] = (dpmax == 0 ? 1 : dpmax+1);
}
int result=*max_element(dp,dp+dat.size());
cout << result << endl;
}
不难看出，两种写法的时间复杂度都是\(O(L^2)\)，这个无疑是很大的，所以不出所料这两个版本的代码在acwing的oj中都会超时，但pat的水oj可以ac。接下来介绍可以在\(O(MN)\)的时间复杂度中求解的LCS做法。