线性DP
线性DP（部分）
例：aw272 LCIS
272. 最长公共上升子序列 - AcWing题库
思路分析:
题目是LCS与LIS的结合，那么我们显然可以结合两道经典例题的思路, 定义f[i] [j] 表示，在a[1...i] 与 b[1...j] 中出现的以B[j]为结尾的数字。
随后我们先遍历a[i]，再遍历b[j], 接下来分两种情况讨论，
①如果a[i] != b[j]， 那么显然此时f[i] [j] = f[i-1] [j], 就以b[j]为结尾的情况和a[i-1]时一样。
②如果a[i] == b[j]，那么此时我们是以b[j]为结尾，我们应该从一个以小于b[j]的b[k]为结尾的最大子串转移而来，因此遍历f[i-1] [k] ，\(1\leq k\leq j-1,且b[k]
优化：
时间复杂度优化: 在寻找f[i-1] [k] 时显然我们重复查找了很多遍，并且我们发现在查找时，i是不变的, 那么对于每一层i来说，我们可以定义变量maxv，用maxv来保存1-j的最大f[i-1] [k]，如果b[j] < a[i] (需要用到maxv去更新的时候a[i] == b[j])，那么我们就更新maxv的值为max(maxv, f[i-1] [j])
代码示例：
int a[3005];
int b[3005];
int n;
int dp[3010][3010];
int main ()
{
cin >> n;
For(i, 1, n) cin >> a[i];
For(i, 1, n) cin >> b[i];
For(i, 1, n)
{
int maxv = 0;
For(j, 1, n)
{
if(a[i] != b[j]) dp[i][j] = dp[i-1][j];
else dp[i][j] = maxv + 1;
if(b[j] < a[i]) maxv = max(maxv, dp[i][j]);
}
}
int ans = 0;
For(i, 1, n)
ans = max(ans, dp[n][i]);
cout << ans << endl;
return 0;
}
空间复杂度优化：由于我们每一层的dp[i] [j]只与上一层dp[i-1]有关，因此我们可以把第一维去掉
代码示例：
int a[3005];
int b[3005];
int n;
int dp[3010];
int main ()
{
cin >> n;
For(i, 1, n) cin >> a[i];
For(i, 1, n) cin >> b[i];
For(i, 1, n)
{
int maxv = 0;
For(j, 1, n)
{
if(a[i] == b[j]) dp[j] = maxv + 1;
if(b[j] < a[i]) maxv = max(maxv, dp[j]);
}
}
int ans = 0;
For(i, 1, n)
ans = max(ans, dp[i]);
cout << ans << endl;
return 0;
}
例：C - Monkey and Banana
思路分析：
由于我们要求最大高度，可以利用贪心的思想，从下往上让底的长和宽尽可能的大，由题意可知， 一组xyz，可以生成三种积木，我们将所有种类的积木放进数组并进行排序，排序条件是长和宽要尽可能的大。随后题目变成了求最长上升子序列的题目，套模板求解即可
代码示例：
//#pragma comment(linker, "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)
#include
#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define Fod(i,b,a) for (int i=(b);i>=(a);--i)
#define mls multiset
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define itt iterator
#define lowbit(x) x & (-x)
#define clr(x) memset(x, 0, sizeof(x));
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAXN = 0x7fffffff;
const int MOD = 1000000007;
struct node
{
int x, y, z;
bool operator < (const node &t) const
{
if(x == t.x) return y < t.y;
return x < t.x;
}
};
vector v;
void add(int x, int y, int z)
{
node t;
t.x = x, t.y = y, t.z = z;
v.push_back(t);
}
int f[10000];
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
int cnt = 0;
while(cin >> n, n)
{
cnt++;
clr(f);
v.clear();
int x, y, z;
For(i, 1, n)
{
cin >> x >> y >> z;
add(x, y, z);
add(x, z, y);
add(y, z, x);
add(y, x, z);
add(z, x, y);
add(z, y, x);
}
sort(v.begin(), v.end());
int k = v.size();
for(int i = 0; i < k; i ++)
{
f[i] = v[i].z;
for(int j = 0; j <= i - 1; j ++)
{
if(v[j].x < v[i].x && v[j].y < v[i].y)
f[i] = max(f[i], f[j] + v[i].z);
}
}
int ans = 0;
For(i, 0, k-1) ans = max(ans, f[i]);
printf("Case %d: maximum height = %d\n", cnt, ans);
}
return 0;
}
LIS 记录路径
例：kuangbin带你飞]专题十二 基础DP1 - Virtual Judge (ppsucxtt.cn)
LIS方法：
//#pragma comment(linker, "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)
#include
#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define Fod(i,b,a) for (int i=(b);i>=(a);--i)
#define mls multiset
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define itt iterator
#define lowbit(x) x & (-x)
#define clr(x) memset(x, 0, sizeof(x));
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAXN = 0x7fffffff;
const int MOD = 1000000007;
const ll MOD1 = 212370440130137957ll;
struct node
{
int w, s, id;
bool operator < (const node &x) const
{
if(s == x.s) return w < x.w;
return s > x.s;
}
}mouse[1005];
int f[1005];
int pos[1005];
int listt[1005];
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n = 1;
int ww, ss;
while(scanf("%d%d", &ww, &ss) != EOF)
{
mouse[n].w = ww, mouse[n].s = ss;
mouse[n].id = n;
n ++;
}
n--;
sort(mouse + 1, mouse + 1 + n);
int len = 0;
For(i, 1, n)
{
f[i] = 1;
For(j, 1, i - 1)
{
if(mouse[j].s > mouse[i].s && mouse[j].w < mouse[i].w)
f[i] = max(f[i], f[j] + 1);
}
len = max(len, f[i]);
}
cout << len << endl;
int anslen = len;
int tag = 0;
Fod(i, n, 1)
{
if(f[i] == len)
{
listt[++tag] = mouse[i].id;
len --;
}
if(len == 0) break;
}
Fod(i, anslen, 1) cout << listt[i] << endl;
return 0;
}
/*
*/
思路分析：先排个序，然后转化成求LIS or LDS。求LIS或者LDS不难，这题重点在于记录路径
方法：求完LIS后逆序遍历dp数组，比如最长长度为5，我们只需逆序遍历找出第一个为5的dp[i]， i即为所求的第五个数字，接下来找出第一个为4的dp[i]....以此类推
这题求LDS方便点，就不用逆序遍历了，最后输出的时候可以直接按照从1到len的顺序输出，因为此时是从左往右正序依次找出长度为len-i的dp[i]，找到直接输出即可。
LDS方法：
//#pragma comment(linker, "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)
#include
#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define Fod(i,b,a) for (int i=(b);i>=(a);--i)
#define mls multiset
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define itt iterator
#define lowbit(x) x & (-x)
#define clr(x) memset(x, 0, sizeof(x));
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAXN = 0x7fffffff;
const int MOD = 1000000007;
const ll MOD1 = 212370440130137957ll;
struct node
{
int w, s, id;
bool operator < (const node &x) const
{
if(w == x.w) return s > x.s;
return w < x.w;
}
}mouse[1005];
int f[1005];
int pos[1005];
int listt[1005];
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n = 1;
int ww, ss;
while(scanf("%d%d", &ww, &ss) != EOF)
{
mouse[n].w = ww, mouse[n].s = ss;
mouse[n].id = n;
n ++;
}
n--;
sort(mouse + 1, mouse + 1 + n);
int len = 0;
Fod(i, n, 1)
{
f[i] = 1;
For(j, i, n)
{
if(mouse[j].s < mouse[i].s && mouse[j].w > mouse[i].w)
f[i] = max(f[i], f[j] + 1);
}
len = max(len, f[i]);
}
cout << len << endl;
For(i, 1, n)
{
if(f[i] == len)
{
cout << mouse[i].id << endl;
len--;
}
if(len == 0) break;
}
cout << endl;
return 0;
}
/*
*/