线性DP
A4paper
·
·
个人记录
模型：
最大子矩阵和：
传送门
将 $i - j$ 行的值压缩到第 $i$ 行。
然后，
就是一维 $DP$ 了。
```cpp
int n;
int f[110];
int a[110][110];
int maxn = -0x3f;
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin >> a[i][j];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
memset(f,0,sizeof(f));
for(int k=1;k<=n;k++)
{
if(i != j) a[i][k] += a[j][k];
//*********最大连续子序列和模型***********
if(f[k-1] > 0) f[k] = f[k-1]+a[i][k];
else f[k] = a[i][k];
//**************************************
if(maxn < f[k]) maxn = f[k];
}
}
cout << maxn;
return 0;
}
```
# 最长单调子序列模型：
[传送门](https://www.luogu.org/problemnew/show/P1020)
首先，
**感谢 $c201904$ 大佬的题解！**
这道题的思路 **极其** 曲折，
第一个输出：
最长下降子序列问题
不解释
第二个输出嘛。。。。
仔细想想好像与第一问差不多，
把小于前面的元素叠合起来，
最后的长度就是答案啦！（其实就是最长上升子序列）
```cpp
int n;
int l,r,mid;
int a[100005];
int f[100005];
int ans1,ans2;
int main()
{
while(scanf("%d",&a[++n]) != EOF) continue;
n--;
f[0] = 0x3f3f3f;
for(int i=1;i<=n;i++)
{
if(f[ans1] >= a[i]) f[++ans1] = a[i];
else //二分
{
l = 0;
r = ans1;
while(l < r)
{
mid = (l+r)/2;
if(f[mid] >= a[i]) l = mid+1;
else r = mid;
}
if(l != 0) f[l] = a[i];
}
}
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++)
{
if(f[ans2] < a[i]) f[++ans2] = a[i];
else //二分
{
l = 0;
r = ans2;
while(l < r)
{
mid = (l+r)/2;
if(f[mid] >= a[i]) r = mid;
else l = mid+1;
}
f[l] = a[i];
}
}
cout << ans1 << endl << ans2;
}
```
# 最长公共子序列模型：
[传送门](https://www.luogu.org/problemnew/show/P1439)
说实话，改来改去有点不像 $DP$ 了，不过好像更好用了
先把第一个序列出现的顺序记下来，
在找第二个序列，如果 $id$ 单增的话说明是公共子序列，
那么，只要找一个最长的就好啦！最长上升子序列！
```cpp
int n,x;
int idx[MAXN],f[MAXN];
int main(void)
{
memset(f,0x3f,sizeof f);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> x;
idx[x] = i;
}
for(int i=1;i<=n;i++)
{
cin >> x;
int id = idx[x];
*lower_bound(f+1,f+1+n,id) = id;
}
int ans = lower_bound(f+1,f+1+n,f[0])-f-1;
cout << ans;
return 0;
}
```
# 题目：
------------
# 巧妙：
[传送门](https://www.luogu.org/problemnew/show/P1282)
这道题的巧妙之处在于它只需要记录总和与第一行的和就可以表示出第二行的和，然后就可以做差，这样就压掉一维，也简化了问题。
于是就有 $DP[i][j]$ 表示前 $i$ 个组成第一行和为 $j$ 的最少交换次数，
于是就有了如下方程：
```cpp
f[i][j] = min(f[i][j],f[i-1][j-a[i]] );
f[i][j] = min(f[i][j],f[i-1][j-b[i]]+1);
```
以及初始化：
```cpp
f[1][a[1]] = 0;
f[1][b[1]] = 1;
```
然后再注意一下边界就 $OK$ 了~~
```cpp
int n,tot,cnt=INF,ans=INF;
int a[MAXN],b[MAXN];
int f[MAXN][6*MAXN];
int main(void)
{
memset(f,0x3f,sizeof f);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i] >> b[i];
tot += a[i]+b[i];
}
f[1][a[1]] = 0;
f[1][b[1]] = 1;
for(int i=2;i<=n ;i++)
for(int j=0;j<=n*6;j++)
{
if(j-a[i] >= 0) f[i][j] = min(f[i][j],f[i-1][j-a[i]] );
if(j-b[i] >= 0) f[i][j] = min(f[i][j],f[i-1][j-b[i]]+1);
}
for(int i=0;i<=tot;i++)
{
if(f[n][i] == INF) continue;
if(abs(2*i-tot) < ans)
{
ans = abs(2*i-tot);
cnt = f[n][i];
}
if(abs(2*i-tot) == ans) cnt = min(cnt,f[n][i]);
}
cout << cnt;
return 0;
}
```