DP基础 - “但愿长醉不愿醒。”

ToTheSun

2026-07-15 21:44:43

发布于：浙江

3阅读

0回复

0点赞

自主学习笔记类产物。并不供他人学习。（也就是说你看不懂我也不会进行修改）

“与君歌一曲，请君为我倾耳听。钟鼓馔玉不足贵，但愿长醉不愿醒。”

Profits S

https://www.luogu.com.cn/problem/P3009
题目大意：一共有n个数，求连续数段最大值。

大致思路是使用一个变量 $f$ 去存储目前的数值，一个变量 $ans$ 存储最终的答案。对于当前的 $f[i]$ ，我们有两个选择：
1.保存前面的，加上它
2.丢弃前面的，只选它

也就是说我们有了（似乎是）状态转移方程： $f=max(f+a[i],a[i])$
但是也不难发现最终的 $f$ 可能并不是答案，所以我们在每次 $f$ 进行变化后， $ans=max(ans,f)$

注意：由于 $a[i]$ 有可能小于零，所以 $ans=-1e9$ （初始化）
这道题似乎并不需要开long long ，但是这种求和的题目还是开一下为好。

合唱队行

https://www.luogu.com.cn/problem/P1091

这道题目是板子拼拼乐。
~~不要瞧不起板子拼拼乐~~
先放一下代码，然后讲一下我的思路（和我觉得要注意的点）

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+5;
int a[N],dp1[N],dp2[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		dp1[i]=1;
		for(int j=1;j<i;j++){
			if(a[j]<a[i])dp1[i]=max(dp1[i],dp1[j]+1);
		}
	}
	for(int i=n;i>=1;i--){
		dp2[i]=1;
		for(int j=i+1;j<=n;j++){
			if(a[i]>a[j])dp2[i]=max(dp2[i],dp2[j]+1);
		}
	}
	int ans=INT_MAX;
    //
	for(int i=1;i<=n;i++){
		ans=min(ans,n-dp1[i]-dp2[i]+1);
	}
	cout<<ans;
	return 0;
}