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<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
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;
        else 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<n;i++)
            num[i]=s[i]-'0';
        for(i=0;i<n;i++)//初始化 取i到最后一位 肯定只有一种
        {
            dp[i][n-1][0]=1;
            dp[i][n-1][1]=1;
        }
        for(i=n-2;i>=0;i--)
        {
            for(j=i;j<n-1;j++)
            {
                k=j+1;
                for(p=k;p<n;p++)
                {
                    int tmp=is(i,j,k,p);
                    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);
                }
           // printf("i:%d j:%d %d %d\n",i,j,dp[i][j][0],dp[i][j][1]);
            }
        }
        ans=0;
        for(i=0;i<n;i++)
            ans=max(ans,dp[0][i][0]);
        printf("%d\n",ans-1);
    }
    return 0;
}

补充：软件开发 , C++ ,