dp模板大全（欢迎来补充）

#include<bits/stdc++.h>
using namespace std;
/*
dp[i]表示以第i个数结尾的最大字段和
dp[i]=max(dp[i],for(int j=i-1;j>=1;j--)dp[i]+a[j];
*/
const int N=2e5+100;
long long dp[N];
int a[N];
int max(long long k,long long l){
	if (k>l) return k;
	else return l;
}
int main(){
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	dp[1]=a[1];
	for (int i=2;i<=n;i++){
		dp[i]=max(dp[i-1]+a[i],a[i]);
	}
	long long ans=LLONG_MIN;
	for (int i=1;i<=n;i++) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}

const int N=1e5+100;
int n, m, w[N], v[N], dp[N];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	}
	cout << dp[m];
}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	for (int i = 1; i <= n; i++) {
		for (int j = w[i]; j <= m; j++) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	}
	cout << dp[m];
}

cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> c[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= c[i]; j <<= 1) w1[++n1] = w[i] * j, v1[n1] = v[i] * j, c[i] -= j;
		if (c[i]) w1[++n1] = w[i] * c[i], v1[n1] = v[i] * c[i];
	}
	for (int i = 1; i <= n1; i++) {
		for (int j = m; j >= w1[i]; j--) dp[j] = max(dp[j], dp[j - w1[i]] + v1[i]);
	}
	cout << dp[m];

for (int k = 1; k <= y; k++) {
			for (int j = s; j >= 0; j--) {
				for (int i = 1; i <= cnt[k]; i++) {
					int idx = f[k][i];
					if (j >= w[idx]) dp[j] = max(dp[j], dp[j - w[idx]] + v[idx]);
				}
			}
		}

 // 求最长上升子序列长度
    for(int i=1;i<=n;i++){
	    for(int j=0;j<i;j++){
	    	if(a[j]<a[i]){ // 如果满足递增要求就更新
	    		dp1[i] = max(dp1[i],dp1[j]+1); // 判断拼接转移后长度是否更长
			}
		}
	}

 for(int i=n;i>0;i--){
	    for(int j=n+1;j>i;j--){
	    	if(a[j]<a[i]){
				dp2[i]=max(dp2[i],dp2[j]+1); // 判断拼接转移后长度是否更长
			}
		}
    }