首页 > ACM题库 > HDU-杭电 > HDU 4105-Electric wave-动态规划-[解题报告]HOJ
2015
04-16

HDU 4105-Electric wave-动态规划-[解题报告]HOJ

Electric wave

问题描述 :

Ali was doing a physic experiment which requires him to observe an electric wave. He needs the height of each peak value and valley value for further study (a peak value means the value is strictly larger than its neighbors and a valley value means the value is strictly smaller than its neighbors). He did write these numbers down but he was too careless that he wrote them in a line without separations, such as “712495” may represent “7 12 4 9 5”. The only information he can remember was:
1. The data begins with a valley value
2. Each value is either a peak value or a valley value
Now he wants to insert blanks to make the data valid. If multiple solutions exist, he will choose the one with more blanks.

输入:

The input consists several testcases.
The first line contains one integer N (1 <= N <= 100), the length of the data.
The second line contains one string S, the data he recorded.
S contains only digits.

输出:

The input consists several testcases.
The first line contains one integer N (1 <= N <= 100), the length of the data.
The second line contains one string S, the data he recorded.
S contains only digits.

样例输入:

6
712495

样例输出:

4
Hint
The separated data may have leading zeros.

转载注明出处  http://blog.csdn.net/moedane

传送门 http://acm.hdu.edu.cn/showproblem.php?pid=4105

题意

给一个长度为n的数字串,在其中加尽可能多的空格,使得分隔出来的数字呈现波谷、波峰、波谷、波峰……这样的规律(即小、大、小、大……这里的大小都是严格的)。求能添加的最多的空格数。n <= 100

思路

o(n^3)的dp。

我的状态设为dp[i][j][2],表示做到前i个数字,且最后一个数字在原串中的区间是[j,i],且最后一个数是波峰/波谷(1/0)的时候,分割成的数字个数。

那么转移就是

dp[i][j][0] = max(dp[j-1][k][1] + 1), [j,i] < [k,j-1]

dp[i][j][1] = max(dp[j-1][k][0] + 1), [j,i] > [k,j-1]

由于题目要求第一个数字必须是波谷,则初始化为

dp数组memset为负无穷大,且dp[i][0][0] = 1,( 0 <= i < n)

答案就是max(dp[n-1][i][0] , dp[n-1][i][1]),( 0 <= i < n)

在转移的时候需要比较两个数的大小,写一个比较的函数即可。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>
#include <map>
#include <set>
#define bug puts("here");

using namespace std;

typedef long long ll;

const int maxn = 2 * 101000;
const ll mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const double PI = atan(1.0) * 4.0;
const double eps = 1e-8;

int dp[110][110][2];
char s[110];
int n;

int scmp(int a,int b,int x, int y){ // [a,b] < [x,y] : -1
    while(s[a]  == '0' && a <= b) a++;
    while(s[x]  == '0' && x <= y) x++;
    if(b-a > y-x) return 1;
    if(b-a < y-x) return -1;
    while(s[a]  == s[x]  && a <= b && x <= y){
        a ++;
        x ++;
    }
    if(a <= b && x <= y)
        return s[a]  < s[x]  ? -1 : 1;
    else if (x <= y) return -1;
    else if (a <= b) return 1;
    else return 0;
}

int main()
{
    while(~scanf("%d",&n))
    {
        scanf("%s",s);
        memset(dp, -0x3f, sizeof dp);
        for(int i=0;i<n;i++) dp[i][0][0] = 1;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                for(int k=0;k<j;k++)
                {
                    if(scmp(k,j-1,j,i) == 1) dp[i][j][0] = max(dp[i][j][0] , dp[j-1][k][1] + 1);
                    if(scmp(k,j-1,j,i) == -1) dp[i][j][1] = max(dp[i][j][1] , dp[j-1][k][0] + 1);
                }
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++)
            ans = max(ans , max(dp[n-1][i][0] , dp[n-1][i][1]));
        printf("%d\n",ans - 1);
    }
}<strong>
</strong>

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/moedane/article/details/37812943