本文主要是介绍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++;//去掉前置0while(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;
}
这篇关于hdu4105 Electric wave的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
