dp打开思路4：POJ1189 UVA12511 HDU2845 HBCPC K

墨蓝 2022-05-16 09:42 90阅读 0赞

# POJ1189 #

[http://poj.org/problem?id=1189][http_poj.org_problem_id_1189]

怎么说呢，不算难，但是容易出问题

我一开始的思路是，第一个钉子只有一种情况，然后下面每个钉子：左边有钉子就加左边的情况数，右边有钉子就加右边的情况数，上边没钉子就加就加上上面的情况。（加情况均是因为小球可以到这里）

我们想到的就是概率问题，这样用情况数量做的话，情况数量统计的确实没错，我想最后把某个位置情况除以总情况就好了，其实是不行的，因为每种情况发生的概率是不一样的，这就是我失败的原因。

后来想到其他方法：假设开始就有n个球，然后每次遇到钉子就分散，也就是数量减少一半，其他一样，也就是说左右有钉子都只加上数量的一半，这就解决了概率问题。

dp可以“人人为我”或者“我为人人”，这种思路明显是人人为我，如果是我为人人推的话，会更加简洁，对于每个钉子，

1、下面有钉子的时候：dp\[i+1\]\[j\]+=dp\[i\]\[j\]/2,dp\[i+1\]\[j+1\]+=dp\[i\]\[j\]/2，

2、下面没钉子时：dp\[i+2\]\[j+1\]+=dp\[i\]\[j\]；

操作简单，不贴代码

# UVA 12511 #

题意：最长公共上升子序列LIS，对，你没有听错就是最长上升子序列，两个序列公共的LCS。

思想结合一下咯

LIS设DP[i]表示以第i个数字结尾的最长上升子序列的长度
    DP[i]=max(DP[j]+1){1<=j<=i-1}
    
    LCS设DP[i][j]表示以A串第i个字符结尾以B串第j个字符结尾的最长字串
    当a[i]==b[j]时：DP[i][j]=DP{i-1][j-1]+1;
    当a[i]!=b[j]时：DP[i][j]=max(DP[i-1][j],DP[i][j-1])
    
    LCIS设DP[i][j]表示以a串前i个字符b串的前j个字符且以b[j]为结尾构成的LCIS的长度
    当a[i]!=b[j]时：DP[i][j]=DP[i-1][j]
    当a[i]==b[j]时：DP[i][j]=max(DP[i-1][k])+1 1<=k<=j-1 && b[j]>b[k]

这个值得贴代码：

#include<iostream>
    #include<cstdio>
    #include<string>
    #include<string.h>
    #include<cstring>
    #include<cmath>
    #include<sstream>
    #include<iomanip>
    #include<algorithm>
    #include<vector>
    using namespace std;
    int dp[1005][1005],a[1005],b[1005],i,j,t,n1,n2,maxn; 
    int main() 
    { 
        scanf("%d",&t); 
        while(t--)
        { 
            scanf("%d",&n1); 
            for(i=1;i<=n1;i++) scanf("%d",&a[i]); 
            scanf("%d",&n2);
            for(i=1;i<=n2;i++) scanf("%d",&b[i]); 
            memset(f,0,sizeof(f)); 
            for(i=1;i<=n1;i++) 
            { 
                maxn=0; 
                for(j=1;j<=n2;j++) 
                { 
                    dp[i][j]=dp[i-1][j];//不相等
                    if (a[i]>b[j]&&maxn<dp[i-1][j]) maxn=dp[i-1][j];//更新maxn
                    if (a[i]==b[j]) dp[i][j]=maxn+1;//相等
                } 
            } 
            maxn=0; 
            for(i=1;i<=n2;i++)if(maxn<dp[n1][i])maxn=dp[n1][i];
            printf("%d\n",maxn);
        }
        return 0;
    }

# HDU2845 #

# [http://acm.hdu.edu.cn/showproblem.php?pid=2845][http_acm.hdu.edu.cn_showproblem.php_pid_2845] #

题意：给出n＊m的矩阵 如果选择了其中一个格子就可以得到该格子上的权值

但是它左边和右边的格子就不能选 然后上下两行的格子也不能选择

很简单的dp 无非是选择与不选择 对于每一行来说 选择了j－1的路径 或者 选择j－2的路径

而j－2的路径可以得到当前点的权值

然后对于每一列来说也是选择i-1的行或者是i-2的行的路径即可

#include<iostream>
    #include<stdio.h>
    #include<cstdio>
    using namespace std;
    #define maxn 222222
    int x[maxn],y[maxn];
    int main(){
        int n,m,ox;
        while(~scanf("%d%d",&n,&m)){
            for(int i=2;i<=n+1;++i){
                for(int j=2;j<=m+1;++j){
                    scanf("%d",&ox);
                    x[j]=max(x[j-1],x[j-2]+ox);
                }
                y[i]=max(y[i-1],y[i-2]+x[m+1]);
            }
            printf("%d\n",y[n+1]);
        }
        return 0;
    }

# K Multiple Longest Commom Subsequence #

[http://newoj.acmclub.cn/contests/1359/problem/6][http_newoj.acmclub.cn_contests_1359_problem_6]

题意：最长公共子序列，要求序列每个元素重复k次，比如1122重复两次，111222重复三次。

输入两个字符串和k，输出长度。

最长公共子序列的一个变形。。。

动态规划。设dp\[i\]\[j\]表示a串处理到i位置，b串处理到j位置的答案。预处理出从a串i位置向前数，第k个与i位置数  
字相同的位置p\[i\]，用相同方式处理出B串的q\[i\]。  
则转移方程为dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i\]\[j-1\],dp\[i-p\[i\]\]\[j-q\[j\]\]+1),其中第三种转移必须在a\[i\]=b\[j\]的情况下转移。

[http_poj.org_problem_id_1189]: http://poj.org/problem?id=1189
[http_acm.hdu.edu.cn_showproblem.php_pid_2845]: http://acm.hdu.edu.cn/showproblem.php?pid=2845
[http_newoj.acmclub.cn_contests_1359_problem_6]: http://newoj.acmclub.cn/contests/1359/problem/6