有点死了，没几个不看题解（或问AI或看视频课)会的

笔记

对于区间问题，可以考虑使用区间dp。区间dp的阶段一般有两种方法划分：

  1. 枚举区间开头和结尾
  2. 枚举区间长度和区间开头（或结尾)，计算出区间的结尾（或开头)

同时，如果遇到环dp问题，可以尝试断环为链（可以将数组复制一遍接在后面)

Luogu P1004 [NOIP 2000 提高组] 方格取数

这题和那个传纸条那题有些类似，但不同，这个是两条路线可以有交点的

#include<bits/stdc++.h>

using namespace std;

const int N = 20;
int a[N][N],f[N][N][N][N];

int main(){
	int n;
	scanf("%d",&n);
	while(true){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(x == 0 && y == 0 && z == 0){
			break;
		}
		a[x][y] = z;
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			for(int k = 1;k <= n;k++){
				for(int l = 1;l <= n;l++){
					f[i][j][k][l] = max({f[i-1][j][k-1][l],f[i][j-1][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1]})+a[i][j]+a[k][l];
					if(i == k && j == l){
						// 由于只能往下或往右，所以如果两条路径经过同一个点，则一定是重合的两条路径
						f[i][j][k][l] -= a[i][j];
					}
				}
			}
		}
	}
	printf("%d",f[n][n][n][n]);
	return 0;
}

Luogu P1435 [IOI 2000] 回文字串

问了以下deepseek。这题还是有一点意思的。

我最初的思路是将字符串分割成左右两个部分，将一个部分翻转一下，然后做只有插入的编辑距离，但我似乎把这题想单纯了，然后我就想明白了这样不行，然后问了deepseek。

定义：ss为字符串，nn为字符串的长度

  • 阶段：按照子串长度划分
  • 状态：fi,j=si...jf_{i,j} = s_{i...j}的部分转换为回文串至少插入的字符个数
  • 转移方程：分两种情况讨论：
    1. si=sjs_i = s_j，则fi,j=fi+1,j−1f_{i,j} = f_{i+1,j-1}
    2. si≠sjs_i \neq s_j，则fi,j=min(fi+1,j,fi,j−1)+1f_{i,j}=min(f_{i+1,j},f_{i,j-1})+1
  • 边界：此题似乎没有边界

最后输出f0,n−1f_{0,n-1}即可

#include<bits/stdc++.h>

using namespace std;

const int N= 1010;
char s[N];
int f[N][N];

int main(){
	scanf("%s",s);
	int n = strlen(s);
	for(int k = 2;k <= n;k++){
		// k表示子串长度
		for(int i = 0;i < n;i++){
			int j = i+k-1;
			if(j >= n){
				break;
			}
			if(s[i] == s[j]){
				f[i][j] = f[i+1][j-1];
			} else{
				f[i][j] = min(f[i+1][j],f[i][j-1])+1;
			}
//			printf("f[%d][%d] = %d\n",i,j,f[i][j]);
		}
	}
	printf("%d",f[0][n-1]);
	return 0;
}

Luogu P1775 石子合并（弱化版）

定义：mm表示读入的序列，nn表示序列的长度

  • 阶段：和上题类似，就是必须按照长度遍历
  • 状态：fi,j=mi...jf_{i,j} = m_{i...j}合并的最小代价
  • 转移方程：这里就直接放伪代码了好吧：fi,j=inffor(i...j){fi,j=min(fi,j,fi,k+fk+1,j)}fi,j=fi,j+∑jl=ial\text{这里就直接放伪代码了好吧：}\\f_{i,j}=inf\\for(i...j)\{\\f_{i,j}=min(f_{i,j},f_{i,k}+f_{k+1,j})\\\}\\f_{i,j} = f_{i,j}+\sum^{l = i}_{j}a_{l}
  • 边界：这题似乎也没有边界
#include<bits/stdc++.h>

using namespace std;

const int N = 310;
int m[N],f[N][N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d",&m[i]);
	}
	for(int k = 2;k <= n;k++){
		for(int i = 1;i <= n;i++){
			int j = i+k-1,sum = 0;
			if(j > n){
				break;
			}
			f[i][j] = INT_MAX;
			for(int l = i;l <= j;l++){
				f[i][j] = min(f[i][j],f[i][l]+f[l+1][j]);
				sum += m[l];
			}
			f[i][j] += sum;
		}
	}
	printf("%d",f[1][n]);
	return 0;
}

Luogu P1220 关路灯

也是看了视频课好吧。

对于关到某个时间节点，我们会发现，如果所关的部分不是连续的，则一定不是最优的，所以就可以把这题转换为区间问题。

  • 阶段：从中间往两边遍历
  • 状态：fi,j,0f_{i,j,0}表示关闭从ii至jj的区间且最后人在左边（即ii上)的最小代价。fi,j,1f_{i,j,1}表示关闭从ii至jj的区间且最后人在右边（即jj上)的最小代价
  • 转移方程：有点长，就直接看代码吧
  • 边界：当i=ci=c并且j=cj = c时，fi,j,0/1=0f_{i,j,0/1} = 0（由于这题需要将ff的所有元素设置为infinf，所以这种情况是需要考虑的）
#include<bits/stdc++.h>

using namespace std;

const int N = 55;
int m[N],w[N];
int f[N][N][2];
int pre[N],sub[N];

int main(){
	memset(f,0x3f,sizeof f);

	int n,c;
	scanf("%d%d",&n,&c);
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&m[i],&w[i]);
		pre[i] = pre[i-1]+w[i];
	}
	for(int i = n;i >= 1;i--){
		sub[i] = sub[i+1]+w[i];
	}
	for(int l = c;l >= 1;l--){
		for(int r = c;r <= n;r++){
			if(l == c && r == c){
				f[l][r][0] = 0;
				f[l][r][1] = 0;
			} else{
				// 转移方程
				if(l != c){
					f[l][r][0] = min({f[l+1][r][0]+(m[l+1]-m[l])*(pre[l]+sub[r+1]),f[l+1][r][1]+(m[r]-m[l])*(pre[l]+sub[r+1])});
				}
				if(r != c){
					f[l][r][1] = min({f[l][r-1][1]+(m[r]-m[r-1])*(pre[l-1]+sub[r]),f[l][r-1][0]+(m[r]-m[l])*(pre[l-1]+sub[r])});
				}
			}
//			printf("f[%d][%d][0] = %d\n",l,r,f[l][r][0]);
//			printf("f[%d][%d][1] = %d\n\n",l,r,f[l][r][1]);
		}
	}
	printf("%d",min(f[1][n][0],f[1][n][1]));
	return 0;
}

Luogu P4342 [IOI 1998] Polygon

这题有点复杂，不太会

Luogu P1880 [NOI1995] 石子合并

我们只需要对那个弱化版做一个环处理即可（哦，还要处理最大值)

#include<bits/stdc++.h>

using namespace std;

const int N = 210;
int m[N],f[N][N],g[N][N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d",&m[i]);
		m[n+i] = m[i];
	}
	for(int k = 2;k <= 2*n;k++){
		for(int i = 1;i <= 2*n;i++){
			int j = i+k-1,sum = 0;
			if(j > 2*n){
				break;
			}
			f[i][j] = INT_MAX;
			for(int l = i;l <= j;l++){
				f[i][j] = min(f[i][j],f[i][l]+f[l+1][j]);
				g[i][j] = max(g[i][j],g[i][l]+g[l+1][j]);
				sum += m[l];
			}
			f[i][j] += sum;
			g[i][j] += sum;
		}
	}
	int mx = 0,mn = INT_MAX;
	for(int i = 1;i <= n;i++){
		mn = min(mn,f[i][i+n-1]);
		mx = max(mx,g[i][i+n-1]);
	}
	printf("%d\n%d",mn,mx);
	return 0;
}

Luogu P6064 [USACO05JAN] Naptime G

这题呢其实细想还是蛮好做的，不过我还是看了题解，又对着AI调试

是看了这篇题解，思路就不想说了

#include<bits/stdc++.h>

using namespace std;

const int N = 4000;
int u[N],f[N][N][2];
int n,b,ans;
void dp(){
	for(int i = 2;i <= n;i++){
		f[i][0][0] = 0;
		for(int j = 1;j <= b;j++){
			f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]);
			f[i][j][1] = max(f[i-1][j-1][0],f[i-1][j-1][1]+u[i]);
		
//			printf("f[%d][%d][0] = %d\n",i,j,f[i][j][0]);
//			printf("f[%d][%d][1] = %d\n\n",i,j,f[i][j][1]);
		}
	}
//	ans = max({ans,f[n][b][1],f[n][b][0]});
}

int main(){
	scanf("%d%d",&n,&b);
	for(int i = 1;i <= n;i++){
		scanf("%d",&u[i]);
	}
	memset(f,-0x3f,sizeof f);
	f[1][1][1] = 0;
	f[1][0][0] = 0;
	dp();
	ans = max({ans,f[n][b][1],f[n][b][0]});
	memset(f,-0x3f,sizeof f);
	f[1][1][1] = u[1];
	f[1][0][0] = 0;
	dp();
	ans = max({ans,f[n][b][1]});
	printf("%d",ans);
	return 0;
}
/*
7 6
150000
160000
170000
140000
180000
190000
200000

ans: 880000
*/