hdu4105 Electric wave

题意;

给一串连续的数 向其中加空格 使之分成符合 波谷 波峰 波谷 波峰。。依次排列的数

波谷即与之相邻两数比它大 波峰即相邻的数比它小

dp[i][j][0、1] 表示以第 i 到第 j 位之间表示的数为波谷或波峰所得到的最大值

dp方程：

int tmp=is(i,j,k,p);// 求 i 到 j 之间构成的数 是否可以作为 k 到 p 之间构成的数（在 i 之后）的波谷 若两数相等 返回0
if(tmp==1)//i j可以当波谷
dp[i][j][0]=max(dp[i][j][0],dp[k][p][1]+1);
else if(tmp<0)//i j可以当波峰
dp[i][j][1]=max(dp[i][j][1],dp[k][p][0]+1);

感想：

又是一道不知道怎么表示dp方程的题。。

搜解题报告 只有四篇 一篇dp是一维的 一篇dp是二维的 一篇dp是三维的 还有一篇是贪心。。

然后一篇都看不懂。。试了下他们的程序可以0ms过 我这个虽然比男神的优化了一点点 还是要109ms。。

男神说 哪里处理起来麻烦 就在哪里设置状态

最起码的一条是怎样利用自己设置的状态的子结构 得到当前状态的值

经验。。以后可以多试试

#include
#include
#include
#include
#include
#include
using namespace std;

int dp[105][105][2],n,num[105];
char s[105];

int is(int i,int j,int k,int p)
{
    while(num[i]==0) i++;//去掉前置0
    while(num[k]==0) k++;
    if(k>p) return -1;//不可能。。
    if(i>j) return 1;
    if((j-i)<(p-k)) return 1;//先用长度判断大小
    if((j-i)>(p-k)) return -1;
    for(int l=0;l<=(j-i);l++)//每位比较
    {
        if(num[l+i]num[k+l]) return -1;
    }
    return 0;//说明每一位都相等 既不是波峰也不是波谷
}

int main()
{
    int i,j,k,p,ans;
    while(~scanf("%d",&n))
    {
        getchar();
        gets(s);
        if(n==1)//优化一下。。
        {
            printf("0\n");
            continue;
        }
        if(n==2)
        {
            if(s[0]>s[1]) printf("0\n");
            else printf("1\n");
            continue;
        }
        memset(dp,0,sizeof dp);
        for(i=0;i=0;i--)
        {
            for(j=i;j