线性dp总结1

此处总结的是  矩阵类地图和LIS LCS问题

 何时能用： dp一定是最优解 因为dp是得到了所有的情况 只不过取了最优的答案，所以三种属性一定满足，即 数量/max/min  

也可以用来判断是否存在的合法性 见题目3 即dp[i][j]=1 即代表这个状态的合法

注意dp得到了模型之后，下次再见到类似的题目就可以直接套用模型   

模型1  ###K

矩阵模型， 一般为可以向右走和可以向下走  转移状态显然

1. 题目链接：http://noi.openjudge.cn/ch0206/8786/  矩阵取数的加强版，要求走两条路径，要注意处理重复的问题

dp[k][i][j] 代表两条路径各自的横纵坐标之和为k 第一条在第i行，第二条在第j行 当且仅当i==j的时候 说明两条路径重合，此时需要少加一个数

然后 分析法 分为 下下 下右 右下 右右 4种情况转移过来即可

 1 #include
 2 using namespace std;
 3 const int maxn=1e1+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 int mp[maxn][maxn];
12 int dp[maxn*2][maxn][maxn];
13 
14 
15 
16 
17 
18 int main()
19 {
20     ios::sync_with_stdio(0);
21     cin.tie(0);
22     int n;
23     cin>>n;
24     int a,b,c;
25     while(cin>>a>>b>>c)
26     {
27         if(!a&&!b&&!c) break;
28         mp[a][b]=c;
29     }
30     for(int k=2;k<=2*n;k++)
31     {
32         for(int i1=1;i1<=n;i1++)
33         {
34             for(int i2=1;i2<=n;i2++)
35             {
36                 int j1=k-i1,j2=k-i2;
37                 if(j1<1||j1>n||j2<1||j2>n) continue;
38                 int v=mp[i1][j1];
39                 if(i1!=i2) v+=mp[i2][j2];
40                 int &x=dp[k][i1][i2];
41                 x=max(x,dp[k-1][i1-1][i2-1]);
42                 x=max(x,dp[k-1][i1-1][i2]);
43                 x=max(x,dp[k-1][i1][i2-1]);
44                 x=max(x,dp[k-1][i1][i2]);
45                 x+=v;
46             }
47         }
48     }
49     cout<'\n';
50 
51 
52 
53 }

模型2

用来转移状态来判断某个状态是否合法

1.题解传送门：https://www.cnblogs.com/winfor/p/14091721.html

模型3

LIS问题

 1.题目链接：http://noi.openjudge.cn/ch0206/4977/  把问题转换成往左跑 是开头到以i为结尾的LIS  

往右跑 是 以n为起点 i为结尾的LIS 求两次LIS 取max即可

 1 #include
 2 #define ll long long
 3 #define pb push_back
 4 using namespace std;
 5 const int maxn=1e5+10;
 6 const int mod=1e9+7;
 7 int dp[111];
 8 int a[maxn],b[maxn];
 9 
10 
11 
12 int main()
13 {
14     ios::sync_with_stdio(0);
15     cin.tie(0);
16     int t;
17     cin>>t;
18     while(t--)
19     {
20         int n;
21         cin>>n;
22         for(int i=1;i<=n;i++)
23         {
24             cin>>a[i];
25         }
26         int ans=0;
27         for(int i=1;i<=n;i++)
28         {
29             dp[i]=1;
30             for(int j=1;j)
31             {
32                 if(a[i]>a[j])
33                     dp[i]=max(dp[i],dp[j]+1);
34             }
35             ans=max(ans,dp[i]);
36         }
37 
38         for(int i=1;i<=n;i++)
39         {
40             b[i]=a[n-i+1];
41         }
42 
43         for(int i=1;i<=n;i++)
44         {
45             dp[i]=1;
46             for(int j=1;j)
47             {
48                 if(b[i]>b[j])
49                     dp[i]=max(dp[i],dp[j]+1);
50             }
51             ans=max(ans,dp[i]);
52         }
53         cout<'\n';
54 
55 
56     }
57 
58 
59 
60 
61 
62 }

 2.题目链接：https://codeforces.ml/contest/1350/problem/B

数论结合的LIS问题  求出调和级数的复杂度 nlogn 每个数的因子  然后跑普通的LIS 时间复杂度 n*平均因子数 平均因子数大概是log级别的

需要nlogn解决的LIS问题

注意 如果求的是上升子序列 那么要用lower_bound 否则可能会越界  而求的是最长不降子序列(非严格最长上升子序列)

要注意用upper_bound 否则会WA  2 3 3 2 这种会导致d数组意义错误 2代替了2 实际应该是2代替3

1.题目链接：https://www.luogu.com.cn/problem/P2782 可以把问题转换成根据a[i].first 排序后 求a[i].second的LIS

 1 #include
 2 #define ll long long
 3 #define pb push_back
 4 #define fi first
 5 #define sc second
 6 using namespace std;
 7 const int maxn=2e5+10;
 8 const int mod=1e9+7;
 9 pair<int,int>a[maxn];
10 int d[maxn];
11 
12 
13 int main()
14 {
15     ios::sync_with_stdio(0);
16     cin.tie(0);
17     int n;
18     cin>>n;
19     for(int i=1;i<=n;i++)
20     {
21         cin>>a[i].fi>>a[i].sc;
22     }
23     sort(a+1,a+1+n);
24     int len=1;
25     d[1]=a[1].sc;
26     for(int i=2;i<=n;i++)
27     {
28         int x=a[i].sc;
29         if(x>d[len])
30         {
31             d[++len]=x;
32         }
33         else
34         {
35             int p=lower_bound(d+1,d+1+len,x)-d;
36             d[p]=x;
37         }
38     }
39     cout<'\n';
40 
41 
42 
43 
44 
45 
46 
47 
48 }

2.题目链接：https://atcoder.jp/contests/abc165/tasks/abc165_f  树上LIS 通过回溯 所以遍历一遍树得到LIS 每次还原d数组即可

注意还原 不是只还原长度， 更改的d[p] 也要记录下来 并且还原

 1 #include
 2 #define ll long long
 3 #define pb push_back
 4 #define fi first
 5 #define sc second
 6 using namespace std;
 7 const int maxn=2e5+10;
 8 const int mod=1e9+7;
 9 int a[maxn];
10 vector<int>E[maxn];
11 int d[maxn];
12 int len=1;
13 int ans[maxn];
14  
15 void dfs(int u,int fa)
16 {
17     ans[u]=len;
18     int bl=len;
19     int num=0;
20     for(auto &v:E[u])
21     {
22         if(v==fa)
23             continue;
24         int p;
25         if(a[v]>d[len])
26         {
27             d[++len]=a[v];
28         }
29         else
30         {
31             p=lower_bound(d+1,d+1+len,a[v])-d;
32             num=d[p];
33             d[p]=a[v];
34         }
35         dfs(v,u);
36         len=bl;
37         if(num)
38             d[p]=num;
39     }
40 }
41  
42  
43  
44 int main()
45 {
46     ios::sync_with_stdio(0);
47     cin.tie(0);
48     int n;
49     cin>>n;
50     for(int i=1;i<=n;i++)
51         cin>>a[i];
52     for(int i=1;i)
53     {
54         int x,y;
55         cin>>x>>y;
56         E[x].pb(y);
57         E[y].pb(x);
58     }
59     d[1]=a[1];
60     dfs(1,0);
61     for(int i=1;i<=n;i++)
62         cout<'\n';
63  
64  
65  
66  
67  
68 }

 模型4

LCS问题

1.题解传送门：https://www.cnblogs.com/winfor/p/13991555.html  普通的LCS问题

2.把LCS问题转化成LIS问题 可以nlogn求解

模型5

编辑距离问题

增删改 3种操作   dp[i][j] 代表a从1~i b从1~j 能够匹配上的需要的最少操作次数

首先考虑初始化  dp[i][0]=i 因为只能使用删除操作 dp[0][i]=i 因为只能删除操作

然后 增加操作的话  考虑当前已经到 a[i] 和b[j]  如果要增加一个使得匹配上  a[i]和b[j-1] 就一定要是匹配上的 所以是 dp[i][j-1]+1

删除操作的话  dp[i-1][j]+1 同理  ， 然后  修改操作的话 就是dp[i-1][j-1] 然后改a[i]=b[j] 即可  当然如果a[i]==b[j] 本来就成立就不需要改了

 1 #include
 2 using namespace std;
 3 const int maxn=1e3+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 int n,m;
12 char a[maxn],b[maxn];
13 int dp[maxn][maxn];
14 
15 
16 int main()
17 {
18     ios::sync_with_stdio(0);
19     cin.tie(0);
20     cin>>n>>(a+1);
21     cin>>m>>(b+1);
22     for(int i=1;i<=n;i++) dp[i][0]=i;
23     for(int i=1;i<=m;i++) dp[0][i]=i;
24     for(int i=1;i<=n;i++)
25     {
26         for(int j=1;j<=m;j++)
27         {
28             dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1);
29             dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i]!=b[j]));
30         }
31     }
32     cout<'\n';
33 
34 
35 
36 }

杂项

题目 1.https://www.cnblogs.com/winfor/p/13530979.html  但有些情况下需要一点贪心来帮助确认状态

比如排序后 让最大的先两两组合 再来dp确定取和不取 

2.https://www.cnblogs.com/winfor/p/13519110.html  因为要转移 来定义能够被转移的状态 

如进行操作需要前面全部是1 所以需要定义前面全是1的状态  答案要求的是所有为0的状态