注册 登录
编程论坛 → C++教室

求助一道动态规划题目

RKNO 发布于 2018-11-22 18:56， 2851 次点击
题目大意如下：(其他描述被我略过，只剩下核心问题)
有一堵长度为n块砖的墙，现在要把墙拆掉，每次拆掉最外围的砖块(不太好描述，下面有样例解释)，
问要拆几次才可以把墙拆掉？

输入格式：
第1行输入墙的长度n（1≤n≤10^5）
第2行输入n个数Mi，分别对应每个单位长度墙的高度（1≤Mi≤10^9）

输出格式：
输出次数m

输入样例：
10
3 1 2 4 6 5 2 1 4 2

输出样例：
4

样例解释：
见图：
第1次拆掉的打叉
第2次拆掉的打三角
第3次拆掉的打井号
第4次拆掉的打圈
总共需要4次
只有本站会员才能查看附件，请 登录
10 回复
#2
rohalloway2018-11-22 21:37
只有本站会员才能查看附件，请 登录


提供一个思路：
将输入的mi转成字符串，取mi中最大的值，比如示例输入的6

000111        000000        000000        000000        000000
000001        000000        000000        000000        000000
000011        000001        000000        000000        000000
001111        000011        000001        000000        000000
111111  ->    001111  ->    000011  ->    000001  ->    000000
011111        000011        000001        000000        000000
000011        000001        000000        000000        000000
000001        000000        000000        000000        000000
001111        000001        000000        000000        000000
000011        000000        000000        000000        000000

第一次输入完后就是第一列的样式
程序代码：

string IntToString(int n, int max)
{
    string str = "";
    for (int i = 0; i < max - n; i++)
    {
        str += "0";
    }

    for (int j = 0; j < n; j++)
    {
        str += "1";
    }

    return str;
}



程序代码：

int FindFirstOne(const string str)
{
    int i = 0;
    for (; i < str.length(); i++)
    {
        if (str[i] == '1')
            break;
    }
    return i;
}




FindFirstOne的返回值就是字符串中第一个为1的位置
最后根据FindFirstOne的返回值分别检查 str[i+1]、str[i-1]、下一行字符串str2[i]和上一行字符串str1[i]中的值是否为'0'

也就是分别判断上下左右是否为'0'

若为'0'则更新str[i] = '0';


方法比较笨，但是算是个思路吧。
#3
RKNO2018-11-22 21:47
回复 2楼 rohalloway
谢谢你提供的思路，毫无疑问，在数据规模较小的情况下可以这样写。
但是现在面临一个问题就是Mi能取到10的9次方，这个思路就不成立了。是吧？
#4
rohalloway2018-11-22 22:31
以下是引用RKNO在2018-11-22 21:47:19的发言：

谢谢你提供的思路，毫无疑问，在数据规模较小的情况下可以这样写。
但是现在面临一个问题就是Mi能取到10的9次方，这个思路就不成立了。是吧？



这道题我研究了半天也没想出来可行的数学算法

所以就有了这个笨方法


你要是解决了把推理过程发上来分享一下

[此贴子已经被作者于2018-11-22 22:33编辑过]
#5
RKNO2018-11-22 22:42
回复 4楼 rohalloway
嗯，我也研究了半天，但是解决不了超时的问题，看到这个数据规模我人都傻了。
#6
rjsp2018-11-23 11:56
才 10^5 个，我觉得数量不大，先写个最简单的，等有时间再仔细想想，今天比较忙

程序代码：
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main( void )
{
    unsigned wall[100000];
    unsigned n;

    // 输入
    scanf( "%u", &n );
    for( size_t i=0; i!=n; ++i )
        scanf( "%u", &wall[i] );

    // 处理
    unsigned max_count = 0;
    for( size_t i=0; i!=n; ++i )
    {
        unsigned count = wall[i];
        for( unsigned j=1; j<count; ++j )
        {
            unsigned left = i>=j ? wall[i-j] : 0 ;
            unsigned right = i+j<n ? wall[i+j] : 0;
            count = min( count, min(left,right)+j );
        }
        max_count = max( max_count, count );
    }
   

    // 输出
    printf( "%u\n", max_count );
}



[此贴子已经被作者于2018-11-23 13:34编辑过]
#7
RKNO2018-11-23 13:10
高手就是不一样。给你点个赞。我还没有细看你的代码，我今早也想了个方案，刚刚做出来提交过了，哈哈。。
以下附上我朴素的思路以及代码：

思路：
定义一个数组dp[],存放每一列最底下一块砖第几次被拆掉。
这个数值被2种情况影响
1、头顶上的砖被拆掉了，就轮到最后一块砖了
2、左边或右边一列最后一块砖被拆掉了，也轮到此列的砖被拆

一开始我们定义一个结构体a，保存输入数据，并保存下标(因为我下面用到了排序)
dp[]数组初始化为：min{当前列砖的数量，当前列到两个边界的最小距离};
为什么要取到边界的最小距离呢？因为每拆一次，边界那两列砖必定被拆掉。
然后对结构体数组排序。从砖数量少的列数开始处理，更新两边的状态，详细的处理看代码吧。
程序代码：
#include <cstdio>
#include <algorithm>
#define MAXN 100000
using namespace std;
struct Data
{
    long long bricks;//存放数据(每一列砖的高度)
    int index;//存放数组下标
};
struct Rule//按砖的高度，从小到大排序
{
    bool operator()(const Data &s1, const Data &s2)
    {
        if (s1.bricks < s2.bricks)
            return true;
        else
            return false;
    }
};
Data a[MAXN+10];
long long dp[MAXN+10];
int main(void)
{
    int n;
    long long i;
    scanf("%d", &n);//墙的长度
    for (i=1; i<=n; ++i)
    {
        scanf("%lld", &a[i].bricks);//输入每一类砖的高度
        dp[i] = a[i].bricks;
        a[i].index = i;//保存下标
    }
    //dp[]初始化
    for (i=1; i<=n/2; ++i)
        dp[i] = min(dp[i], i);
    for (i=n; i>n/2; --i)
        dp[i] = min(dp[i], n+1-i);
    //从小到大排序
    sort(a+1, a+n+1, Rule());
    int Max=0;
    for (i=1; i<=n; ++i)
    {
        //更新左边的dp[]
        if (dp[a[i].index]+1<dp[a[i].index-1])
            dp[a[i].index-1] = dp[a[i].index]+1;
        //更新右边的dp[]
        if (dp[a[i].index]+1<dp[a[i].index+1])
            dp[a[i].index+1] = dp[a[i].index]+1;
    }
    //找出dp[]中最大的一个
    for (i=1; i<=n; ++i)
    {
        if (dp[i]>Max)
            Max = dp[i];
    }
    printf("%d", Max);//输出
    return 0;
}
#8
rjsp2018-11-23 14:11
回复 7楼 RKNO
我写了两个不同的方法，测试下来，效率差不多。
你的代码如果能封装成 unsigned foo1( unsigned wall[], unsigned n ) 这种形式的话，也可以放进来测试一下算法效率。

程序代码：
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

// 方法一：计算第i堵墙的墙跟到最近边缘的距离，返回其中的最大值
unsigned foo1( unsigned wall[], unsigned n )
{
    unsigned max_count = 0;
    for( size_t i=0; i!=n; ++i )
    {
        unsigned count = wall[i];
        for( unsigned j=1; j<count; ++j )
        {
            unsigned left = i>=j ? wall[i-j] : 0 ;
            unsigned right = i+j<n ? wall[i+j] : 0;
            count = min( count, min(left,right)+j );
        }
        max_count = max( max_count, count );
    }
    return max_count;
}

// 方法二：模拟拆砖过程，每次去掉最外层的砖
unsigned foo2( unsigned wall[], unsigned n )
{
    unsigned count = 0;
    for( ;; )
    {
        // 去掉两边的 0
        for( ; n!=0 && wall[0]==0; ++wall, --n );
        for( ; n!=0 && wall[n-1]==0; --n );
        if( n == 0 )
            break;

        // 腐蚀一次
        unsigned height = wall[0]; // 原先左边的高度
        for( unsigned i=1; i<n-1; ++i )
        {
            unsigned old = wall[i];
            wall[i] = min( min(height,wall[i+1]), max(wall[i],1u) - 1u );
            height = old;
        }
        wall[0] = 0;
        wall[n-1] = 0;
        ++count;
    }
    return count;
}

// 测试谁的效率高
#include <ctime>
void test( unsigned (*fun)(unsigned wall[], unsigned n) )
{
    time_t t0 = time(NULL);

    unsigned tmp = 0;
    for( unsigned a=0; a!=10; ++a )
    for( unsigned b=0; b!=10; ++b )
    for( unsigned c=0; c!=10; ++c )
    for( unsigned d=0; d!=10; ++d )
    for( unsigned e=0; e!=10; ++e )
    for( unsigned f=0; f!=10; ++f )
    for( unsigned g=0; g!=10; ++g )
    for( unsigned h=0; h!=10; ++h )
    for( unsigned i=0; i!=10; ++i )
    {
        unsigned wall[] = { a,b,c,d,e,f,g,h,i };
        tmp += fun( wall, sizeof(wall)/sizeof(*wall) );
    }

    time_t t1 = time(NULL);
    printf( "%u ", tmp ); // 防止编译器直接优化掉
    printf( "耗时: %lld\n", (long long)(t1-t0) );
}

int main( void )
{
    test( foo1 );
    test( foo2 );
}
#9
RKNO2018-11-23 19:45
妙啊，两种方法都很好。。只是为什么我的电脑跑不出结果。

[此贴子已经被作者于2018-11-23 19:49编辑过]
#10
rjsp2018-11-24 10:24
回复 9楼 RKNO
我用十多年的破电脑测试，大约2分钟运行完毕
#11
RKNO2018-11-24 19:46
嗯，原来要等这么久。谢谢了。
1
©2025, BC-CN.NET
电脑版