dp打开思路：HDU1029 HDU1087 HDU1176 HDU1257 POJ1458（水题不水）

缺乏、安全感 2022-05-17 00:27 291阅读 0赞

题目：https://vjudge.net/contest/68966#overview

HDU - 1029

题意：找出出现次数超过一半的数字

蠢思路：排序找中间

DP：扫一遍一个变量count记录解出现的次数，是当前解就++，否则—，count为负就换掉当前解。（解释：想象解全都挨在一起（前面），count先达到最大，然后减为1或0，而其他数字先出现，可能会使正确解的count减为负数，但都会使正确解在后面更多，从而保证了结束时肯定为正确解）代码拿来

  1. //在代码可读性较好的前提下才追求代码简洁，所以没有缩哦
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. int main()
  6. {
  7.     int n;
  8.     while(scanf("%d",&n)!=EOF){
  9.         int temp,k=0;
  10.         int count=0;
  11.         while(n--){
  12.             scanf("%d",&temp);
  13.             if(temp==k)count++;
  14.             else{
  15.                 count--;
  16.                 if(count<0){
  17.                     count=0;
  18.                     k=temp;
  19.                 }
  20.             }
  21.         }
  22.         printf("%d\n",k);
  23.     }
  24. }

HDU 1087

题意：找递增子序列的最大和

思路：和最长递增子序列类似，只是dp[i]=max(之前的)+第i个数的值。

HDU - 1176 

题意：略，百度原题自己看

思路：dp[t][x] 表示第t秒第x个位置上有馅饼掉落，把所有馅饼都填入表，从底往上走，走到最上面，求经过和最大。

注：刚开始想不到是这种题，还是思维不够开啊，用二维表示时间和一维空间，很巧妙。（萌新跳转https://blog.csdn.net/hebtu666/article/details/79964233第二题）

HDU - 1257 

题意：就是求一个最长上升子序列啊

解释：对于这个最长上升子序列而言，每一个数代表一个拦截系统的最小值，并且由于序列是上升的，每一个数都不能再拦截序列中的下一个数，因为下一个数更大，因此这个子序列的长度就是拦截系统数。

注：我原来以为是找最长下降子序列并对剩下的数递归，直到没有数字，看有几个序列。是我脑子不够活。

poj-1458

最长公共子序列

经典题

核心代码

dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1;

发表评论

表情：
评论列表 （有 0 条评论，291人围观）

还没有评论，来说两句吧...

相关阅读

    相关 hdu1176 dp

    免费馅饼问题。 分析： 一道比较简单的dp问题，只要想到用dp\[i\]\[j\]去表示第i秒走到位置j所得到的最多馅饼数，这道题目也就解决了。 状态转移方程是： dp

    ╰半夏微凉°╰半夏微凉°/ 0 赞/ 348 阅读