动态规划1LIS,LCS,数字三角形模型

目录

 一、数字三角形

Acwing1027 方格取数

状态划分为最后一步，两个点分别向右、上移动（2^2），共四种情况。

Acwing275.传纸条

二、LIS

Acwing 1012.友好城市

Acwing 1010.拦截导弹

Acwing 187.导弹拦截系统

Acwing 272.最长公共上升子序列

---

 一、数字三角形

Acwing1027 方格取数

 思路：可以走两次，也可以同时走两条路，本次采用同时走的方式

令k为走的步数，即k==i1 j1=i2 j2。表示从两条路从（1,1）走到（i1，j1）（i2，j2）的最大值

状态划分为最后一步，两个点分别向右、上移动（2^2），共四种情况。

由于走过之后数被取走，因此取数时如果两个点重合了（i2==i1），则t只加一次。

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #include<cstring>
4.  
   //k表示为i j。。状态表示为两条路从1,1分别走到i1,j1、i2,j2的最大值
5.  
   //状态划分为四种（2*2）
6.  
   //如果两个点重叠了，t就只加一次，否则加两次
7.  
   using namespace std;
8.  
    
9.  
   const int N =12;
10.  
    int f[2*N][N][N];
11.  
    int w[N][N];
12.  
    int n;
13.  
     
14.  
    int main()
15.  
    {
16.  
    cin>>n;
17.  
    int a,b,c;
18.  
    while(cin>>a>>b>>c,a||b||c)
19.  
    w[a][b]=c;
20.  
     
21.  
    for(int k=2;k<=n n;k )
22.  
    for(int i1=1;i1<=n;i1 )
23.  
    for(int i2=1;i2<=n;i2 )
24.  
    {
25.  
    int j1=k-i1,j2=k-i2;
26.  
    if(j1>=1&&j1<=n&&j2>=1&&j2<=n)
27.  
    {
28.  
    int t=w[i1][j1];
29.  
    if(i1!=i2) t =w[i2][j2];
30.  
    int &x=f[k][i1][i2];
31.  
    x=max(x,f[k-1][i1-1][i2-1] t);
32.  
    x=max(x,f[k-1][i1][i2-1] t);
33.  
    x=max(x,f[k-1][i1-1][i2] t);
34.  
    x=max(x,f[k-1][i1][i2] t);
35.  
    }
36.  
    }
37.  
    cout<<f[2*n][n][n];
38.  
    return 0;
39.  
    }
40.  
     
41.  
     
42.  
    作者：yankai
43.  
    链接：https://www.acwing.com/activity/content/code/content/4036790/
44.  
    来源：AcWing
45.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Acwing275.传纸条

 总结：类似方格取数，不过严格要求不能走到同一个点，走过某个点之后数不会被取走。

1.  
   //这里填你的代码^^
2.  
   #include<iostream>
3.  
   #include<algorithm>
4.  
   #include<cstring>
5.  
   using namespace std;
6.  
   const int N =55;
7.  
   int g[N][N];
8.  
   int f[2*N][N][N];
9.  
   int n,m;
10.  
    /*首先考虑路径有交集该如何处理。
11.  
    可以发现交集中的格子一定在每条路径的相同步数处。因此可以让两个人同时从起点出发，每次同时走一步，这样路径中相交的格子一定在同一步内。
12.  
     
13.  
    状态表示：f[k, i, j] 表示两个人同时走了k步，第一个人在 (i, k - i) 处，第二个人在 (j, k - j)处的所有走法的最大分值。
14.  
     
15.  
    状态计算：按照最后一步两个人的走法分成四种情况：
16.  
     
17.  
    两个人同时向右走，最大分值是 f[k - 1, i, j] score(k, i, j)；
18.  
    第一个人向右走，第二个人向下走，最大分值是 f[k - 1, i, j - 1] score(k, i, j)；
19.  
    第一个人向下走，第二个人向右走，最大分值是 f[k - 1, i - 1, j] score(k, i, j)；
20.  
    两个人同时向下走，最大分值是 f[k - 1, i - 1, j - 1] score(k, i, j)；
21.  
    注意两个人不能走到相同格子，即i和j不能相等。
22.  
     
23.  
    作者：yxc
24.  
    链接：https://www.acwing.com/solution/content/3954/
25.  
    来源：AcWing
26.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
27.  
     
28.  
    int main()
29.  
    {
30.  
    cin>>n>>m;
31.  
    for(int i=1;i<=n;i )
32.  
    for(int j=1;j<=m;j )
33.  
    cin>>g[i][j];
34.  
     
35.  
    for(int k=2;k<=n m;k )
36.  
    for(int i=max(1,k-m);i<=n&&i<k;i )
37.  
    for(int j=max(1,k-m);j<=n&&j<k;j )
38.  
    for(int a=0;a<=1;a )
39.  
    for(int b=0;b<=1;b )
40.  
    {
41.  
    int t=g[i][k-i];
42.  
    if(i!=j||k==2||k==n m)
43.  
    {
44.  
    t =g[j][k-j];
45.  
    f[k][i][j]=max(f[k][i][j],f[k-1][i-a][j-b] t);
46.  
    }
47.  
    }
48.  
    cout<<f[n m][n][n];
49.  
    return 0;
50.  
     
51.  
    }
52.  
    //注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
53.  
     
54.  
    作者：yankai
55.  
    链接：https://www.acwing.com/activity/content/code/content/4037889/
56.  
    来源：AcWing
57.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二、LIS

Acwing 1012.友好城市

 分析：取两对友好城市，假设x1<x2，要使得不相交，则需要y1<y2。题目要求则转化为，求最多对同时满足x1<x2,y1<y2的方案。若友好城市按x递增排序，则转化为求y数组的LIS。

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   #include<algorithm>
4.  
   using namespace std;
5.  
    
6.  
   const int N =5010;
7.  
   typedef pair<int,int> PII;
8.  
    
9.  
   PII city[N];
10.  
    int f[N];
11.  
    int n;
12.  
     
13.  
    int main()
14.  
    {
15.  
    cin>>n;
16.  
    for(int i=0;i<n;i )
17.  
    {
18.  
    int x,y;
19.  
    cin>>x>>y;
20.  
    city[i]={x,y};
21.  
    }
22.  
     
23.  
    sort(city,city n);
24.  
     
25.  
    int res=0;
26.  
     
27.  
    for(int i=0;i<n;i )
28.  
    {
29.  
    f[i]=1;
30.  
    for(int j=0;j<i;j )
31.  
    if(city[i].second>city[j].second)
32.  
    f[i]=max(f[i],f[j] 1);
33.  
    res=max(res,f[i]);
34.  
    }
35.  
    cout<<res;
36.  
    return 0;
37.  
    }
38.  
     
39.  
    作者：yankai
40.  
    链接：https://www.acwing.com/activity/content/code/content/4038147/
41.  
    来源：AcWing
42.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Acwing 1010.拦截导弹

与贪心结合：遇到一个导弹时，由拦截高度比导弹高的系统中，高度最低的拦截。若拦截不了，就用新的系统拦截。

证明：若某一步贪心解与最优解不同，则最后，两段能够交换，不会产生新的系统。

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   using namespace std;
4.  
    
5.  
   const int N =1e5 10;
6.  
   int f[N],g[N];
7.  
   int n;
8.  
   int a[N];
9.  
   int main()
10.  
    {
11.  
    while(cin>>a[n]) n ;
12.  
     
13.  
    int len=0;
14.  
    f[0]=-2e9;
15.  
    for(int i=0;i<n;i )
16.  
    {
17.  
    int l=0,r=len;
18.  
    while(l<r)
19.  
    {
20.  
    int mid=l r 1>>1;
21.  
    if(f[mid]>=a[i]) l=mid;
22.  
    else r=mid-1;
23.  
    }
24.  
    len=max(len,r 1);
25.  
    f[r 1]=a[i];
26.  
    }
27.  
    cout<<len<<endl;
28.  
     
29.  
    int res=0;
30.  
    int cnt=0;
31.  
    for(int i=0;i<n;i )
32.  
    {
33.  
    int k=0;
34.  
    while(k<cnt&&g[k]<a[i]) k ;
35.  
    g[k]=a[i];
36.  
    if(k>=cnt) cnt ;
37.  
    }
38.  
    cout<<cnt;
39.  
    }
40.  
     
41.  
    作者：yankai
42.  
    链接：https://www.acwing.com/activity/content/code/content/4043034/
43.  
    来源：AcWing
44.  
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Acwing 187.导弹拦截系统

 贪心原理与上题相同，但是本次我们并不能判断是加入下降子序列中还是上升子序列中。解决方法是直接爆搜。需注意本题爆搜代码的编写

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #include<cstring>
4.  
   using namespace std;
5.  
   //思路同上一题 但由于不知道放入上升或下降系统中，因此直接爆搜求得答案
6.  
   const int N =55;
7.  
    
8.  
   int n;
9.  
   int up[N],down[N];
10.  
    int q[N];
11.  
    int ans;
12.  
     
13.  
     
14.  
    void dfs(int u,int su,int sd)//位置，当前上升子序列数量、下降子序列数量
15.  
    {
16.  
    if(su sd>=ans) return; //这个分支不可能更新答案
17.  
    if(u==n)
18.  
    {
19.  
    ans=su sd;
20.  
    return;
21.  
    }
22.  
     
23.  
    //情况1 加到上升子序列中
24.  
    int k=0;
25.  
    while(k<su&&up[k]>=q[u]) k ;//严格单调 因此>=
26.  
    int t=up[k];
27.  
    up[k]=q[u];
28.  
    if(k<su) dfs(u 1,su,sd);
29.  
    else dfs(u 1,su 1,sd);
30.  
    up[k]=t; //恢复现场
31.  
     
32.  
     
33.  
    //情况2 加入下降子序列中
34.  
    k=0;
35.  
    while(k<sd&&down[k]<=q[u]) k ;
36.  
    t=down[k];
37.  
    down[k]=q[u];
38.  
    if(k<sd) dfs(u 1,su,sd);
39.  
    else dfs(u 1,su,sd 1);
40.  
    down[k]=t;
41.  
    }
42.  
     
43.  
    int main()
44.  
    {
45.  
    while(cin>>n,n)
46.  
    {
47.  
    for(int i=0;i<n;i )
48.  
    cin>>q[i];
49.  
     
50.  
    ans=n;
51.  
     
52.  
    dfs(0,0,0);
53.  
    cout<<ans<<endl;
54.  
    }
55.  
    }

Acwing 272.最长公共上升子序列

 结合LIS和LCS，用f[i,j]表示a序列中前i个数字选择，以bj结尾的最长公共上升子序列。

状态划分f[i,j]：

• 若不选择ai，则为f[i-1,j]
• 若选择ai。要计算该情况则需要再细分，细分为结尾是b1~bj-1的最长公共上升子序列（为保证上升，需要bk<bj才能加入决策集合），即：

则循环体朴素写法为：

1.  
   for(int i=1;i<=n;i )
2.  
   for(int j=1;j<=n;j )
3.  
   {
4.  
   f[i][j]=f[i-1][j];
5.  
   if(a[i]==b[j])
6.  
   {
7.  
   f[i][j]=max(f[i][j],1);
8.  
   for(int k=1;k<j;k )
9.  
   {
10.  
    if(b[k]<b[j]) //等价于b[k]<a[i]
11.  
    f[i][j]=max(f[i][j],f[i][k] 1);
12.  
    }
13.  
    }
14.  
    }

注意到第二层与第三层循环可以合并。

把0<=k<j,b[k]<a[i] 的k构成的集合称为f[i,j]转移时的决策集合；

注意到在第二层循环j增加到m时，第一层循环i是个定值，即b[k]<a[i]是固定的。因此j增加1时，k的取值范围从0~j变为0~j 1，，即j可能进入新的决策集合。

也就是说只需要检查b[j]<a[i]是否成立，已经在决策集合中的数则一定不会去除。

简单解释：保存符合条件的f[i,k]的最大值maxv。j即将增大时，判断b[j]<a[i]，若成立则f[i-1][j]也可能在决策集合里。即maxv=max(maxv,f[i-1][j])。

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #include<cstring>
4.  
   using namespace std;
5.  
    
6.  
   const int N =3010;
7.  
   int n;
8.  
   int a[N],b[N],f[N][N];
9.  
    
10.  
    int main()
11.  
    {
12.  
    cin>>n;
13.  
    for(int i=1;i<=n;i ) cin>>a[i];
14.  
    for(int i=1;i<=n;i ) cin>>b[i];
15.  
     
16.  
    /*for(int i=1;i<=n;i )
17.  
    for(int j=1;j<=n;j )
18.  
    {
19.  
    f[i][j]=f[i-1][j];
20.  
    if(a[i]==b[j])
21.  
    {
22.  
    f[i][j]=max(f[i][j],1);
23.  
    for(int k=1;k<j;k )
24.  
    {
25.  
    if(b[k]<b[j]) //等价于b[k]<a[i]
26.  
    f[i][j]=max(f[i][j],f[i][k] 1);
27.  
    }
28.  
    }
29.  
    }
30.  
    */
31.  
     
32.  
    //把0<=k<j,b[k]<a[i] 的k构成的集合称为f[i,j]转移时的决策集合
33.  
    //注意到在第二层循环j增加到m时，第一层循环i是个定值，即b[k]<a[i]是固定的。
34.  
    //因此j增加1时，k的取值范围从0~j变为0~j 1，，即j可能进入新的决策集合。
35.  
    //也就是说只需要检查b[j]<a[i]是否成立，已经在决策集合中的数则一定不会去除。
36.  
     
37.  
    //简单解释：保存符合条件的f[i,k]的最大值maxv。
38.  
    //j即将增大时，判断b[j]<a[i]，若成立则f[i-1][j]也可能在决策集合里。即maxv=max(maxv,f[i-1][j])
39.  
     
40.  
    for(int i=1;i<=n;i )
41.  
    {
42.  
    //val是决策集合中f[i,k]的最大值
43.  
    int val=0;
44.  
     
45.  
    //j==1时，0可以作为k的取值
46.  
    if(b[0]<a[i]) val=f[i-1][0];
47.  
    for(int j=1;j<=n;j )
48.  
    {
49.  
    if(a[i]==b[j]) f[i][j]=val 1;
50.  
    else f[i][j]=f[i-1][j];
51.  
     
52.  
    if(b[j]<a[i]) val=max(val,f[i][j]);
53.  
    }
54.  
    }
55.  
     
56.  
     
57.  
    int res=0;
58.  
    for(int i=1;i<=n;i ) res=max(res,f[n][i]);
59.  
    cout<<res;
60.  
    return 0;
61.  
    }

    

这篇好文章是转载于：学新通技术网