吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 3025|回复: 6
收起左侧

[C&C++ 转载] 动态规划

[复制链接]
KaQqi 发表于 2019-4-16 18:22
本帖最后由 KaQqi 于 2019-4-17 21:40 编辑

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。


题目1:在一个序列中找出一个递增序列的最大长度
[C++] 纯文本查看 复制代码
#include <stdio.h>

int n,data[1000];
int result[10000];

int main()
{
        scanf("%d",&n);
        for(int i = 0;i<n;i++)
        {
                scanf("%d",&data[i]);
                result[i] = 0;
        }
        for(int i = 0;i<n;i++)
        {
                int middle = data[i];
                for(int j = i-1;j>= 0;j--)
                {
                        if(data[j] < data[i])
                        {
                                data[i] = data[j];
                                result[i] ++;
                        }
                }
                data[i] = middle;
        }
        int print = 0;
        for(int i = 0;i<n;i++)
        {
                if(result[i] > print)
                {
                        print = result[i];
                }
        }
        printf("%d",print+1);
}


题目2:导弹拦截 https://www.luogu.org/problemnew/show/P1020
这道题的输入方法来源于@苏紫方璇 大神
[C++] 纯文本查看 复制代码
#include <stdio.h>

int n,data[1000];
int result[10000];

int Calculate()
{
        for(int i = 0;i<n;i++)
        {
                int middle = data[i];
                for(int j = i-1;j>= 0;j--)
                {
                        if(data[j] > data[i])
                        {
                                data[i] = data[j];
                                result[i] ++;
                        }
                }
                data[i] = middle;
        }
        int print = 0;
        for(int i = 0;i<n;i++)
        {
                if(result[i] > print)
                {
                        print = result[i];
                }
        }
        return print+1;
}

int main()
{
        
        for(int i = 0;;i++)
        {
                char ch;
                scanf("%d",&data[i]);
                scanf("%c",&ch);
                n++;
                result[i] = 0;
                if(ch == '\n') break;
        }
        int a = Calculate();
        printf("%d\n",a);
}


这道题就是要求一个最长单调不升子序列和一个最长单调上升子序列。
[backcolor=rgba(255, 255, 255, 0.701961)]
[C++] 纯文本查看 复制代码
#include <stdio.h>
 
int n,data[1000];
int result[10000];
 
 
int Calculate2()
{
    for(int i = 0;i<n;i++)
    {
        int middle = data[i];
        for(int j = i-1;j>= 0;j--)
        {
            if(data[j] < data[i])
            {
                data[i] = data[j];
                result[i] ++;
            }
        }
        data[i] = middle;
    }
    int print = 0;
    for(int i = 0;i<n;i++)
    {
        if(result[i] > print)
        {
            print = result[i];
        }
    }
    return print+1;
} 
 
int Calculate1()
{
    for(int i = 0;i<n;i++)
    {
        int middle = data[i];
        for(int j = i-1;j>= 0;j--)
        {
            if(data[j] >= data[i])
            {
                data[i] = data[j];
                result[i] ++;
            }
        }
        data[i] = middle;
    }
    int print = 0;
    for(int i = 0;i<n;i++)
    {
        if(result[i] > print)
        {
            print = result[i];
        }
    }
    return print+1;
}
 
int main()
{
     
    for(int i = 0;;i++)
    {
        char ch;
        scanf("%d",&data[i]);
        scanf("%c",&ch);
        n++;
        result[i] = 0;
        if(ch == '\n') break;
    }
    int a = Calculate1();
    for(int i = 0;i<n;i++) result[i] = 0;
    int b = Calculate2();
    printf("%d\n%d",a,b);
}


然后上面一个代码有点多余重复部分,优化一下。。
[C++] 纯文本查看 复制代码
#include <stdio.h>

int n,data[100000];
int result[100000];


int Calculate2()
{
        for(int i = 0;i<n;i++)
        {
                
                for(int j = 0;j<i;j++)
                {
                        if(data[i]>data[j]&&result[j]+1>result[i]) result[i]=result[j]+1;
                }
        
        }
        int print = 0;
        for(int i = 0;i<n;i++)
        {
                if(result[i] > print)
                {
                        print = result[i];
                }
        }
        return print+1;
} 

int Calculate1()
{
        for(int i = 0;i<n;i++)
        {
                
                for(int j = 0;j<i;j++)
                {
                        if(data[i]<=data[j]&&result[j]+1>result[i]) result[i]=result[j]+1;
                }
        }
        int print = 0;
        for(int i = 0;i<n;i++)
        {
                if(result[i] > print)
                {
                        print = result[i];
                }
        }
        return print+1;
}

int main()
{

        for(int i = 0;;i++)
        {
                char ch;
                scanf("%d",&data[i]);
                scanf("%c",&ch);
                n++;
                result[i] = 0;
                if(ch == '\n') break;
        }
        int a = Calculate1();
        for(int i = 0;i<n;i++) result[i] = 0;
        int b = Calculate2();
        printf("%d\n%d",a,b);
        return 0;
}


[C++] 纯文本查看 复制代码
#include <stdio.h>
#include <cstdio>
#include<iostream>
using namespace std;

int n,data[100000];
int result[100000];
int result2[100000];



int main()
{

	while(cin >> data[n])
	{
		result[n] = 0;
		n++;
		
	}
	for(int i = 0;i<n;i++)
	{

		for(int j = 0;j<i;j++)
		{
			if(data[i]<=data[j]&&result[j]+1>result[i]) result[i]=result[j]+1;
			if(data[i]>data[j]&&result2[j]+1>result2[i]) result2[i]=result2[j]+1;
		}
	}
	int print1 = 0;
	int print2 = 0;
	for(int i = 0;i<n;i++)
	{
		if(result[i] > print1)
		{
			print1 = result[i];
		}
		if(result2[i] > print2)
		{
			print2 = result2[i];
		}
	}

	printf("%d\n%d",print1+1,print2+1);
	return 0;
}


免费评分

参与人数 2吾爱币 +8 热心值 +2 收起 理由
涛之雨 + 3 + 1 用心讨论,共获提升!
苏紫方璇 + 5 + 1 欢迎分析讨论交流,吾爱破解论坛有你更精彩!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

PanTA 发表于 2019-4-16 19:20
我一直在等你的红警,一直等
涛之雨 发表于 2019-4-16 20:57
 楼主| KaQqi 发表于 2019-4-17 19:55
ZQVVVVV 发表于 2019-4-18 15:05
终于看见一个算法帖 好不容易偶
坏坏坏蛋 发表于 2019-4-18 21:00
我要联机红警无限钱,大佬0.0
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:本版块禁止灌水或回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-3-28 22:51

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表