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

举报
兔老大 发表于 2021/04/19 23:06:21 2021/04/19
【摘要】 POJ1189 http://poj.org/problem?id=1189 怎么说呢,不算难,但是容易出问题 我一开始的思路是,第一个钉子只有一种情况,然后下面每个钉子:左边有钉子就加左边的情况数,右边有钉子就加右边的情况数,上边没钉子就加就加上上面的情况。(加情况均是因为小球可以到这里) 我们想到的就是概率问题,这样用情况数量做的话,情况数量统计的确实没错,我想最...

POJ1189

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。

思想结合一下咯


  
  1. LIS设DP[i]表示以第i个数字结尾的最长上升子序列的长度
  2. DP[i]=max(DP[j]+1){1<=j<=i-1}
  3. LCSDP[i][j]表示以A串第i个字符结尾以B串第j个字符结尾的最长字串
  4. a[i]==b[j]时:DP[i][j]=DP{i-1][j-1]+1;
  5. a[i]!=b[j]时:DP[i][j]=max(DP[i-1][j],DP[i][j-1])
  6. LCISDP[i][j]表示以a串前i个字符b串的前j个字符且以b[j]为结尾构成的LCIS的长度
  7. a[i]!=b[j]时:DP[i][j]=DP[i-1][j]
  8. a[i]==b[j]时:DP[i][j]=max(DP[i-1][k])+1 1<=k<=j-1 && b[j]>b[k]

这个值得贴代码:


  
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<string>
  4. #include<string.h>
  5. #include<cstring>
  6. #include<cmath>
  7. #include<sstream>
  8. #include<iomanip>
  9. #include<algorithm>
  10. #include<vector>
  11. using namespace std;
  12. int dp[1005][1005],a[1005],b[1005],i,j,t,n1,n2,maxn;
  13. int main()
  14. {
  15. scanf("%d",&t);
  16. while(t--)
  17. {
  18. scanf("%d",&n1);
  19. for(i=1;i<=n1;i++) scanf("%d",&a[i]);
  20. scanf("%d",&n2);
  21. for(i=1;i<=n2;i++) scanf("%d",&b[i]);
  22. memset(f,0,sizeof(f));
  23. for(i=1;i<=n1;i++)
  24. {
  25. maxn=0;
  26. for(j=1;j<=n2;j++)
  27. {
  28. dp[i][j]=dp[i-1][j];//不相等
  29. if (a[i]>b[j]&&maxn<dp[i-1][j]) maxn=dp[i-1][j];//更新maxn
  30. if (a[i]==b[j]) dp[i][j]=maxn+1;//相等
  31. }
  32. }
  33. maxn=0;
  34. for(i=1;i<=n2;i++)if(maxn<dp[n1][i])maxn=dp[n1][i];
  35. printf("%d\n",maxn);
  36. }
  37. return 0;
  38. }

HDU2845

http://acm.hdu.edu.cn/showproblem.php?pid=2845

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

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

 

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

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

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


  
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<cstdio>
  4. using namespace std;
  5. #define maxn 222222
  6. int x[maxn],y[maxn];
  7. int main(){
  8. int n,m,ox;
  9. while(~scanf("%d%d",&n,&m)){
  10. for(int i=2;i<=n+1;++i){
  11. for(int j=2;j<=m+1;++j){
  12. scanf("%d",&ox);
  13. x[j]=max(x[j-1],x[j-2]+ox);
  14. }
  15. y[i]=max(y[i-1],y[i-2]+x[m+1]);
  16. }
  17. printf("%d\n",y[n+1]);
  18. }
  19. return 0;
  20. }

K Multiple Longest Commom Subsequence 

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]的情况下转移。

 

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/81837461

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。