稍微进阶的区间DP

$f_{i,j}$并不能描述这个状态代表了什么,

但$f_{i,j,w}$可以,即表示$[i,j]$合成到最后的状态为$w$的最大贡献

那么转移时就把$w$拆成$w>>1$和$w\text{&}1$的两种状态。

那么还要考虑$w$状态的限制条件。

可以根据每删$k$则加$1$可知,最后状态决定于$(j-i)\text{mod}(k-1)+1$个字符。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define fin(s) freopen(s".in","r",stdin)
#define I inline 
using namespace std;
const int N=305,M=N<<1;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll f[N][N][N];
int a[N],b[N],c[N];
char s[N]; 
int main()
{ 
    int n,k;qr(n),qr(k);
    for(int i=1;i<=n;i++)qr(c[i]);
    for(int i=0;i<(1<<k);i++)qr(a[i]),qr(b[i]);
    memset(f,0xcf,sizeof(f));
    for(int i=1;i<=n;i++)f[i][i][c[i]]=0;
    for(int len=1;len<n;len++)
        for(int l=1,r,v;l+len<=n;l++)
        {
            r=l+len,v=(r-l)%(k-1)+1;;
            if(v==1)for(int w=0;w<(1<<k);w++)
                for(int x=r-1;x>=l;x-=k-1)
                    f[l][r][a[w]]=max(f[l][r][a[w]],f[l][x][w>>1]+f[x+1][r][w&1]+b[w]);
            else for(int w=0;w<(1<<v);w++)
                for(int x=r-1;x>=l;x-=k-1)
                    f[l][r][w]=max(f[l][r][w],f[l][x][w>>1]+f[x+1][r][w&1]);
        }
    ll ans=0;
    for(int i=0;i<(1<<k);i++)
        ans=max(ans,f[1][n][i]);
    qw(ans);puts("");
    return 0;
}