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

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

题目：[https://vjudge.net/contest/68966\#overview][https_vjudge.net_contest_68966_overview]

[HDU - 1029][]

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

蠢思路：排序找中间

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

//在代码可读性较好的前提下才追求代码简洁，所以没有缩哦
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF){
            int temp,k=0;
            int count=0;
            while(n--){
                scanf("%d",&temp);
                if(temp==k)count++;
                else{
                    count--;
                    if(count<0){
                        count=0;
                        k=temp;
                    }
                }
            }
            printf("%d\n",k);
        }
    }

[HDU 1087][]

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

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

[HDU - 1176 ][HDU - 1029]

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

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

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

[HDU - 1257 ][HDU - 1029]

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

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

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

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;

[https_vjudge.net_contest_68966_overview]: https://vjudge.net/contest/68966#overview
[HDU - 1029]: https://mp.csdn.net/postedit#problem/_blank
[HDU 1087]: https://vjudge.net/problem/17613/origin