线性DP

#include <bits/stdc++.h>
using namespace std;
int a[25];
long long dp[25][2];
/*
3 
100 70 102
dp[3][2]=2 
dp[3][1]=2
*/
int main(){
	int m;
	cin>>m;
	while(m--){
		int n;
		cin>>n;
		for(int i=1;i<=n;++i)cin>>a[i];
		for(int i=1;i<=n;++i){
			dp[i][0]=1;dp[i][1]=1; //每一个都单独成为一段
		}
		for(int i=2;i<=n;++i){
			for(int j=1;j<i;j++){
				if(a[j]<=a[i]){ //可以构成新的不下降子序列
					if(dp[j][0]+1>dp[i][0]){ //一个是长度增加
						dp[i][0]=dp[j][0]+1;
						dp[i][1]=dp[j][1];//方案是继承
					}else if(dp[j][0]+1==dp[i][0]){ //一个是长度相等
						dp[i][1]+=dp[j][1];//我要累加方案
					}
				}
			}
		} 
		int t = 0;
		for(int i=1;i<=n;++i){
			t = max(t,(int)dp[i][0]);
		}
		long long cnt = 0;
		for(int i=1;i<=n;++i){
			if(dp[i][0]==t)cnt+=dp[i][1];
		}
		cout<<t<<" "<<cnt<<endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
/*a[i][j]=第i小组做第j步所需天数
dp[i][j] 第j步由小组i完成时的最少累计天数 
*/
int a[N][N],dp[N][N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	} 
	for(int i=1;i<=m;i++)dp[i][1]=a[i][1];
	for(int j=2;j<=n;++j){
		for(int i=1;i<=m;++i){
			int pre =(i==1)?m:i-1; //这里处理环 
			dp[i][j]=a[i][j]+min(dp[i][j-1],dp[pre][j-1]);//选择从同一小组转移还是从上一个小组转移
		}
	} 
	int ans = INT_MAX;
	for(int i=1;i<=m;++i)ans=min(ans,dp[i][n]);
	cout<<ans<<endl; 
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
double dp[2];
int main(){
	int n;
	cin>>n;
	dp[0]=100.0; //dp[0]表示当前可能拥有的美元最大数量
	dp[1]=0.0;//dp[1]表示当前可能拥有的马克的最大数量
	for(int i=1;i<=n;++i){
		double A;
		cin>>A;
		double usd = max(dp[0],dp[1]*100.0/A);
		double mark = max(dp[1],dp[0]*A/100.0);
		dp[0]=usd; 
		dp[1]=mark;
	}
	cout<<fixed<<setprecision(2)<<dp[0]<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
const int INF = 1e9;
int h[N];
/*
dp[i][0] 跳到第i层的最小时间
dp[i][1] 爬到第i层的最小时间

dp[i][0] = min(dp[i-2][1],dp[i-1][1]);
dp[i][1] = min(dp[i-1][1],dp[i-1][0])+h[i];

*/
int dp[N][2];

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)cin>>h[i];
	dp[0][0]=INF;
	dp[0][1]=0;
	for(int i=1;i<=n;++i){
		int from2 = (i>=2)?dp[i-2][1]:INF;
		dp[i][0]=min(dp[i-1][1],from2);
		dp[i][1]=min(dp[i-1][0],dp[i-1][1])+h[i];
	}
	cout<<min(dp[n][0],dp[n][1])<<endl;
	
	return 0;
}