C++ 线性dp 洛谷_c++线性dp

数字三角形

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 7→3→8→7→57→3→8→7→5 的路径产生了最大权值。

输入格式

第一个行一个正整数 r ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
 
const int N = 1e6+10,M = 2000;
int va[M][M];
int dp[M][M];
 
signed main()
{
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=i;j++)
		{
			cin>>va[i][j];
		} 
	} 
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=i;j++)
		{
			if(dp[i][j]<dp[i-1][j]+va[i][j])
			{
				dp[i][j] = dp[i-1][j]+va[i][j];
			}
			if(dp[i][j]<dp[i-1][j-1]+va[i][j])
			{
				dp[i][j]=dp[i-1][j-1]+va[i][j];
			}
		}			
	}	
	int maxn = 0;
	for(int j = 1;j<=n;j++)
	{
		maxn = max(maxn,dp[n][j]);
	}
	cout<<maxn;
	return 0;
}

Generic Cow Protests

题目描述

约翰家的 n 头奶牛聚集在一起，排成一列，正在进行一项抗议活动。第 i 头奶牛的理智度为 ai​。
约翰希望奶牛在抗议时保持理性，为此，他打算将所有的奶牛隔离成若干个小组，每个小组内的奶牛的理智度总和都要不小于零。
由于奶牛是按直线排列的，所以一个小组内的奶牛位置必须是连续的。请帮助约翰计算一下，最多分成几组。

输入格式

第一行一个正整数 n，表示牛的数目。
接下来 n 行，每行一个整数，表示每个牛的理智度。

输出格式

若存在合法分组方案，输出一行一个整数表示答案；否则输出 Impossible。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
 
const int N = 3e6+10,M = 2000;
const int inf = 1e18;
 
int T,n,m,k;
int va[N];
int dp[N];
int sum[N];
 
signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=1;i<=n;i++) sum[i] = sum[i-1]+va[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=i-1;j++)
		{
			if(sum[i]-sum[j]>=0&&sum[j]>=0)
			{
				if(dp[i]<dp[j]+1)
				{
					dp[i] = dp[j]+1;
				}
			}
		} 
	}
	if(dp[n]==0) cout<<"Impossible";
	else cout<<dp[n];
	return 0;
}

最长上升子序列

题目描述

这是一个简单的动规板子题。

给出一个由 n(n≤5000) 个不超过 106106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 n，表示序列长度。

第二行有 n 个整数，表示这个序列。

输出格式

一个整数表示答案。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
 
const int N = 1e6+10;
int va[N];
int dp[N];
 
signed main()
{
	int n;
	cin>>n;
	IOS;
	for(int i = 1;i<=n;i++) cin>>va[i];
	for(int i = 1;i<=n;i++) dp[i] = 1;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=i-1;j++)
		{
			if(va[j]<va[i])
			{
				if(dp[i]<dp[j]+1) dp[i] = dp[j]+1;
			}
		}
	}	
	int maxn = 0;
	for(int i = 1;i<=n;i++) maxn = max(maxn,dp[i]);
	cout<<maxn;
	return 0;
}

Profits S

题目描述

The cows have opened a new business, and Farmer John wants to see how well they are doing. The business has been running for N (1 <= N <= 100,000) days, and every day i the cows recorded their net profit P_i (-1,000 <= P_i <= 1,000).

Farmer John wants to find the largest total profit that the cows have made during any consecutive time period. (Note that a consecutive time period can range in length from one day through N days.) Help him by writing a program to calculate the largest sum of consecutive profits.

奶牛们开始了新的生意，它们的主人约翰想知道它们到底能做得多好。这笔生意已经做了N（1≤N≤100,000）天，每天奶牛们都会记录下这一天的利润Pi（-1,000≤Pi≤1,000）。

约翰想要找到奶牛们在连续的时间期间所获得的最大的总利润。（注：连续时间的周期长度范围从第一天到第N天）。

请你写一个计算最大利润的程序来帮助他。

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: P_i

输出格式

* Line 1: A single integer representing the value of the maximum sum of profits for any consecutive time period.

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
 
const int N = 1e6+10,M = 2000;
int va[N];
int sum[N];
int dp[N];
 
signed main()
{
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		cin>>va[i];	
		sum[i] = sum[i-1]+va[i];	
	}	
	int minn = 0,maxn = -1e18;
	for(int i = 1;i<=n;i++)
	{
		maxn = max(maxn,sum[i]-minn);
		minn = min(minn,sum[i]);
	}
	cout<<maxn;
	
	return 0;
}

租用游艇

题目描述

长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,⋯,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为r(i,（1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。

输入格式

第一行中有一个正整数 n，表示有 n 个游艇出租站。接下来的 n−1 行是一个半矩阵 r(i,j)（1≤i<j≤n）。

输出格式

输出计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
 
const int N = 3e6+10,M = 2000;
const int inf = 1e18;
 
int T,n,m,k;
int va[M][M];
int dp[N];
 
signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		for(int j=i+1;j<=n;j++)
		cin>>va[i][j];
	}
	dp[1] = 0;
	for(int i=2;i<=n;i++) dp[i] = 1e18;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i-1;j++)
		{
			if(dp[i]>dp[j]+va[j][i])
			{
				dp[i] = dp[j]+va[j][i];
			}
		} 
	}
	cout<<dp[n];
	return 0;
}

红牌

题目描述

某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ，一共包括 N 个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程，每一步政府都派了 M 个工作人员来检查材料。不幸的是，并不是每一个工作人员效率都很高。尽管如此，为了体现“公开政府”的政策，政府部门把每一个工作人员的处理一个申请所花天数都对外界公开。

为了防止所有申请人都到效率高的工作人员去申请。这 M×N 个工作人员被分成 M 个小组。每一组在每一步都有一个工作人员。申请人可以选择任意一个小组也可以更换小组。但是更换小组是很严格的，一定要相邻两个步骤之间来更换，而不能在某一步骤已经开始但还没结束的时候提出更换，并且也只能从原来的小组 I 更换到小组 I+1，当然从小组 M 可以更换到小组 1。对更换小组的次数没有限制。

例如：下面是 3 个小组，每个小组 4 个步骤工作天数：

• 小组 1： 2,6,1,8；
• 小组 2：3,6,2,6；
• 小组 3：4,2,3,6。

例子中，可以选择小组 1 来完成整个过程一共花了2+6+1+8=17天，也可以从小组 2 开始第一步，然后第二步更换到小组 3，第三步到小组 1，第四步再到小组 2，这样一共花了 3+2+1+6=12 天。你可以发现没有比这样效率更高的选择。

你的任务是求出完成申请所花最少天数。

输入格式

第一行是两个正整数 N 和 M，表示步数和小组数。

接下来有 M 行，每行有 N 个非负整数，第 i+1(1≤i≤M) 行的第 j 个数表示小组 i 完成第 j 步所花的天数，天数都不超过 1000000。

输出格式

一个正整数，为完成所有步所需最少天数。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
 
const int N = 3e6+10,M = 2010;
const int inf = 1e18;
 
int T,n,m,k;
int va[M][M];
int dp[M][M];
 
signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		cin>>va[i][j];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		dp[i][j] = 1e18;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(dp[i][j]>dp[i-1][j]+va[j][i])
			{
				dp[i][j] = dp[i-1][j]+va[j][i];
			}
			if(j>=2&&dp[i][j]>dp[i-1][j-1]+va[j][i])
			{
				dp[i][j] = dp[i-1][j-1]+va[j][i];
			}
			if(j==1&&dp[i][j]>dp[i-1][m]+va[j][i])
			{
				dp[i][j] = dp[i-1][m]+va[j][i];
			}
		}
	}
	int minn = 1e18;
	for(int i=1;i<=m;i++) minn  = min(minn,dp[n][i]);
	cout<<minn;
	return 0;
}