动态规划

KaQqi

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


题目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);
}

这道题就是要求一个最长单调不升子序列和一个最长单调上升子序列。

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

PanTA

我一直在等你的红警，一直等

涛之雨

咳咳。日常评分。。

KaQqi

涛之雨 发表于 2019-4-16 20:57
咳咳。日常评分。。

咳咳，日常沉贴

ZQVVVVV

终于看见一个算法帖 好不容易偶

坏坏坏蛋

我要联机红警无限钱，大佬0.0