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;
}