题解 P1584 【魔杖】

Shikita · 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];
}

多多指教