一本通之动态规划合集

1258 数字金字塔
一本通的题目相比与洛谷的题好的多，所以，我们来练习一本通的题目吧
只要把一本通的这些题全部弄透，考场上不用怕
然后再练练搜索，就可以复习了
模板题，数字三角形的动态规划
还有就是这一篇文章我将把他们和一起来解决
其实数字三角形并不难，只需要套公式就好了，数字三角形的公式也不难理解
#include
#include
#include
#include
#include
using namespace std;
const int SIZE=1005;
int a[SIZE][SIZE];
int n;
int f[SIZE][SIZE];
int ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
		}
	}
	for(int i=1;i<=n;i++)
		ans=max(ans,f[n][i]);
	cout< 
1259 最长不下降序列 
当然，这也是一个模板题目
 也就是，这个题，不需要连续，不连续的序列，因为不是子序列，所以不需要连续
 因为f数组是用来记录的长度，我们最后需要求的是具体的每一个数，所以还得 
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
    int n,a[1005],f[1005],maxx;
    int m,k,c[1005],i,j;
    maxx=-inf;
    
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    
    for(i=1;i<=n;i++)//将最长不下降序列存储道f数组里面 
    {
   	    f[i]=1;
   	    for(j=1;jf[i])//不下降并且满足最长序列 
			 f[i]=f[j]+1; 
		}
		if(f[i]>maxx)
		{
		   	maxx=f[i];//求出最长的序列 
		   	k=i;//记录下标 
		} 
	}
	int t=0;
	m=maxx;
	c[t++]=k;
	i=k-1;//c[]数组存储最长不下降序列的每一个下标，m总长度，每次循环完就要-1，i为所有数字下标 
	while(m>1)             
	{
		if(f[i]==m-1&&a[i]<=a[k])//k下标记录上一个数组，i记录当前的数字 
		{//回倒求出下标然后输出每一个元素
			c[t++]=i;//存储下标 
			k=i;//记录一下当前的下标
			m--;
		}
		i--;
	}
	printf("max=%dn",maxx);
	for(i=t-1;i>0;i--)
		printf("%d ",a[c[i]]);
	printf("%dn",a[c[0]]);		
} 

 
1261 城市交通图 
题目不用说了，就是让你求最短路径，但是题目说，让用最优原理来求最短路径，貌似不太理解
 也即是分层求最短路径 
#include 
#include 
using namespace std;
const int N=110;
long long e[N][N],ne[N];
long long dis[N];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) cin>>e[i][j];

	for(int i=1;i=0;i--)
	{
		for(int j=i+1;j<=n;j++)
		{//条件：n与j连通，i与j连通.
			if(dis[i]>e[i][j]+dis[j]&&dis[j]!=123456&&e[i][j]!=0)//能更新就更新 
			{
				ne[i]=j;//存储具体的点 
				dis[i]=e[i][j]+dis[j];//找最短路
			}
		}
	}
	cout<<"minlong="< 
1262 挖地雷 
单向的路径，不存在回路
 设计一个方案让他能挖到最多的雷，所以这就和去年的方格取数差不多啊 
#include
#include
#include
#include
#include
#define N 210
#define INF 0x3f3f3f3f
using namespace std;
int b[N][N];
int w[N],p[N];
int f[N];// 表示挖到地雷最大数 
void print(int k) //输出挖地雷的顺序 
{
	if(k == 0)
	return;
	print(p[k]);
	if(p[k] == 0)//如果是第一个点 直接输出k 否则输出-k 
	cout << k;
	else
	cout << "-" << k; //否则输出-k 
}
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin>>w[i];
		f[i]=w[i];
	}
	int x,y;
	while(scanf("%d%d",&x,&y)!=EOF&&x&&y)
		b[x][y] = 1;//标记路径 
	int maxx=-INF,k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(b[j][i]==1&&f[j]+w[i]>f[i])//j可以到i 且 f[j]+w[i] > f[i]
			{
				f[i]=f[j]+w[i];//保存第i个地窖起挖到的后继最大地雷数 
				p[i]=j;  //j 地窖是i的最优路径，也就是记录最优路径 
			}
		}
		if(f[i]>maxx)//计算挖到最多地雷数 
		{
			maxx=f[i];
			k=i;
		}
	}
	print(k);//输出路径 
	cout< 
1285 最大上升子序列和 
就是一个很模板的题目，通过前面的训练我也有些熟练了 
#include
#include
#include
using namespace std;
const int SIZE=1010;
const int inf=0x7fff; 
int n;
int a[SIZE],f[SIZE]; 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	 } 
	 int maxx=-inf;
	 for(int i=1;i<=n;i++) 
	 {
	 	f[i]=a[i];//初始化
		 for(int j=1;jf[i])//满足上升规律并且满足最大 
		 		f[i]=f[j]+a[i];
		 	maxx=max(maxx,f[i]);
		  } 
	 }
	 cout< 
1265最长公共子序列 
公共序列，还得使得最长 
#include
#include
#include
#include
#include
using namespace std;
const int SIZE=1001;
char a[SIZE],b[SIZE];
int f[SIZE][SIZE];
int main()
{
    scanf("%s%s",&a[1],&b[1]);
    int len_a=strlen(&a[1]);
    int len_b=strlen(&b[1]);
    
    for(int i=0;i<=len_a;i++)
        f[i][0]=0;
    for(int i=0;i<=len_b;i++)
        f[0][i]=0;
    for(int i=1;i<=len_a;i++)
        for(int j=1;j<=len_b;j++)
            if(a[i]==b[j])//找到公共了
                f[i][j]=f[i-1][j-1]+1;//更新序列 
            else 
                f[i][j]=max(f[i-1][j],f[i][j-1]);//不然保存最大的序列
    
    cout< 
1266 机器分配 
当然这个题在洛谷上也有，太好了，终于有题解了
 首先，我先用搜索来做做
 然后再用区间dp来完成 
#include
#include
#include
#include
#include
using namespace std;
int n,m,a[20][20],pau[20],f[20],ans;//f[i]是答案机器数，pau是当前假设的机器数量
void dfs(int Nnum,int Nans,int Nm) 
{//Nnum编号，Nans盈利，Nm是剩余的机器 
	if(Nm<0) return;//边界 
	if(Nnum==n+1)//需要输出了 
	{
		if(Nans>ans) 
		{
			ans=Nans;//存储答案 
			for(int i=1;i<=n;i++) f[i]=pau[i];//具体的分配答案 
		}
		return;
	}
	for(int i=0; i<=m; i++) pau[Nnum]=i,dfs(Nnum+1,Nans+a[Nnum][i],Nm-i);//递归搜索 下一个编号开始搜，计算新的盈利，减去这个表示剩余 
	return;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			scanf("%d",&a[i][j]);//预处理 
	dfs(1,0,m);
	printf("%dn",ans);
	for(int i=1; i<=n; i++) printf("%d %dn",i,f[i]);
	return 0;
}
 
搜索还是比较简单的吧，啊？
 不过，dp同样很简单，当时这个简单，不是那个简单
 设f[i][j]为前i个公司总共分配j台机器的最大利润，也就是我们要求的
 然后呢，方程也没好玩，就是f[i][j]=max(f[i-1][j-k],f[i][j]);
 难就难在怎么处理输出的问题
 因为是字典序最小所以
 设表示的意思为“不给”第i家公司k台机器（k的值域同上），那么状态转移方程需改为：
 f[i][j]=max(f[i][k],f[i-1][k]+graph[i][j-k]);
 而path就是
 设path[i][j][h]
 对于前i个公司共分配j台机器的最优方案，第h个公司应分配多少台机器，当状态发生转移时，更新path数组即可。最终的答案就存放在path[n][m][i]之中 
#include
#include
#include
#include 
using namespace std;
int f[11][16],graph[11][16],path[11][16][11],n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin>>graph[i][j];//预处理 
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)    
            for(int k=0;k<=j;k++)//枚举三个循环 
            {
                if (f[i][j] 
1281 最长上升子序列 
最喜欢这种序列问题，比较简单，好操作好假设好实现 
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5; 
const int INF=9999999;
int a[N],f[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
 
    int maxx=-INF;
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//初始化为1
        for(int j=1;jf[i])//满足上升，并且长度更大
                f[i]=f[j]+1;//更新的长度
        maxx=max(maxx,f[i]);
    }
    cout< 
没什么好解释的了 
1281 最大子矩阵 
貌似这个题很熟悉，前几天练习过一个类似的
 子矩阵不需要解释了吧，球的是最大子矩阵的的和
 我猜这个题可以用搜索，大概时间复杂度是n²，看到时间复杂度是100，那么没问题，先来一下搜索
 说白了，这个做法有点类似于暴力了
 枚举每一个子序列就好了 
#include 
#include 
using namespace std;
#define M 10000
int f[M][M], a[M][M];
int n, ans, maxn;
int main() 
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= n; j++) 
		{
            scanf("%d", &a[i][j]);
            f[i][j] = f[i][j-1] + a[i][j]; //类似于二维前缀和         
        }
    for(int i = 1; i <= n; i++) 
	{
        for(int j = i; j <= n; j++) 
		{
            maxn = 0;
            for(int k = 1; k <= n; k++) 
			{
                maxn += f[k][j] - f[k][i-1];//计算当前序列的和 
                ans = max(maxn, ans);//比较最大的和 
                if(maxn < 0) maxn = 0;
            }
        }
    }
    printf("%dn", ans);
    return 0;
}
 
当然，这种做法，肯定不对，我们需要用正解
 正解是啥
 看看这篇文章的标题 
 
 一本通之动态规划合集 
 
对了，正解就是动态规划！！！！
 二维肯定百搭，我们需要用三维来解决这个题，反正数据小的可怜
 设f[i][j][k]表示第i行中第j列到第k列的数字之和，直接累加即可
 设辅助数组，c[i][j][k]表示以第i行第j列到第k列作为下底边的矩阵之和的最大值
 先求f，类似于线段，再来求c类似于处理面积
 就有点像前缀和了，二维前缀和
 c[i][j][k] = max(c[i][j][k], c[i - 1][j][k] + f[i][j][k]); 
那么答案就是c数组了 
复制代码到粘帖板
#include
#include
#include
#include 
#define LL long long
using namespace std;
int n, a[110][110], f[110][110][110], c[110][110][110], ans;
int main()
{
	ans = -0x3fffffff;
	cin>>n;
	for(int i=1;i<=n;++i)
		for(int j=1;j<= n;++j)	
			cin>>a[i][j];
	for(int i=1;i<=n; ++i)
		for(int j=1;j<=n;++j)
			for(int k=j;k<=n;++k)
				f[i][j][k]=f[i][j][k-1]+a[i][k];//类似于二维前缀和 

	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			for(int k = j; k <= n; ++k)
				c[i][j][k] = max(f[i][j][k], f[i][j][k] + c[i - 1][j][k]), ans = max(ans, c[i][j][k]);//存储最大的和 

	printf("%dn", ans);
	return 0;
}
 
1283 登山 
累死了，做完这三个就去肝whk，今晚英语结业，准备完政治，然后明天数学和物理结业，搜索结业
 后天5日 地理生物 政治历史，开始复习信息
 呜呜呜，累死你爹我了
 这个不就有一点像合唱队形吗
 我们先来分析一下思路哈
 最简单直白的一个条件就是不爬海拔相同的山，也就是没有相等的情况
 也就是说要想浏览尽可能多的景色，他们应该选择上山加上下山的最长路径
 so？
 问题就转化为，找到那一个以它作为末尾的上升序列和以它作为开头的下降序列和最大的那一个点
 太像合唱队列了
 然后用两个循环就能求出来两个序列，最后比较哪一个大 
#include
#include
#include
#include
#include
using namespace std;
int n,maxx;
int a[1001],f[1001],t[1001];
int main()
{
	cin>>n;
	
	for(int i=0;i>a[i];
		f[i]=1;//上升序列 
		t[i]=1;//下降序列 
	}
	for(int i=0;if[i])
				f[i]=f[j]+1;
		}
	}
	for(int i=n-1;i>=0;i--)//以这个点没开头的下降序列 
	{
		for(int j=n-1;j>i;j--)
		{
			if(a[j]t[i])
				t[i]=t[j]+1;
		}
	}
	for(int i=0;i 
1304 数的划分 
不知道的还以为是搜索呢
 哎哎，等等，这不就是搜索吗？！
 是的，就是搜索 
#include
using namespace std;
int n,k,ans;
void dfs(int last,int rest,int h)
{
	if(h==k)//划分到头
	{
		ans++;//更新答案
		return ;
	}
	for(int i=last;i<=rest/(k-h+1);i++)//剪枝
	{
		dfs(i,rest-i,h+1);//枚举搜索
	}
	return ;
}
int main()
{
	cin>>n>>k;
	dfs(1,n,1);
	cout< 
接下来，让我们用dp来解决
 其实，搜索和dp有一种莫名其妙的相似感
 不知道为啥
 设f[i][x] 表示 i 分成 x 个非空的数的方案数 
#include
using namespace std;
int n,k,f[201][7];  //f[k][x] k 分成 x 份 ={f[k-1][x-1],f[k-x][x]}
int main(){
    cin >> n >> k;
    for (int i=1;i<=n;i++) {f[i][1]=1;f[i][0]=1;}
    for (int x=2;x<=k;x++) {f[1][x]=0;f[0][x]=0;}  // 边界
    for (int i=2;i<=n;i++)
        for (int x=2;x<=k;x++)
            if (i>x) f[i][x]=f[i-1][x-1]+f[i-x][x];
            else f[i][x]=f[i-1][x-1];
    cout<
一本通之动态规划合集

C/C++/C#相关栏目本月热门文章
