自动搬运

查看原文

来自洛谷，原作者为

	Shikita **

搬运于2025-08-24 21:26:45，当前版本为作者最后更新于2018-08-23 15:51:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道看似暴力枚举的DP题目

就是求切割得到的贡献最大，并且对每一个木条进行长度的限制，而且单根只能取头或者尾，任意两根之前互不重合，于是就写个DP吧

f[i][j]表示起点不超过i，终点不超过j的所有魔杖魔力之和的最大值。

f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+w[i][j]);

对了提醒一下这题应该开个long long，要不然会WA两个点

代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#define int long long//既然已经写好了代码还一个个去改好烦
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9'){if(c=='-')flag=1;   c=getchar();}
    while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+c-'0';c=getchar();}
    return flag?-x:x;
}
int n,minn,maxn;
int l[1005][1005],w[1005][1005];
int f[1005][1005];
signed main()//由于某种不可描述的原因，就这样看着吧
{
	n=read(),minn=read(),maxn=read();
	for(int i=1;i<=n;++i) l[i][i]=read();
	for(int i=1;i<=n;++i) w[i][i]=read();
    //由于用二维处理，那么这些干脆都用个二维储存
	for(int i=1;i<=n;++i)
	  for(int j=i+1;j<=n;++j)
	  {
	  	l[i][j]=l[i][j-1]+l[j][j];
	  	w[i][j]=w[i][j-1]+w[j][j];
	  }//前缀和压缩
	for(int i=1;i<=n;++i) 
	  for(int j=i;j<=n;++j)
	  	if(l[i][j]<minn||l[i][j]>maxn) w[i][j]=0;
    //求的是max那就把初值变为0
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=n;++j)
	  	f[i][j]=max(f[i-1][j],max(f[i][j-1],f[i-1][j-1]+w[i][j]));
    //状态转移方程
	cout<<f[n][n];
}

多多指教