题目描述
有一个长度为
n
n
n 的
01
01
01 串，你可以每次将相邻的
k
k
k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这
k
k
k 个字符确定。你需要求出你能获得的最大分数。
数据范围
1
≤
n
≤
300
,
0
≤
c
i
≤
1
,
w
i
≥
1
,
k
≤
8
1 \leq n \leq 300, \ 0 \leq c_i \leq 1, \ w_i \geq 1, \ k \leq 8
1≤n≤300, 0≤ci≤1, wi≥1, k≤8
题解
数据范围较小，考虑区间
d
p
dp
dp ，
f
l
,
r
,
s
f_{l,r,s}
fl,r,s 表示
[
l
,
r
]
[l,r]
[l,r] 最后合并成状态
s
s
s 的最大分数，可以通过
l
,
r
l,r
l,r 知道
s
s
s 的长度
考虑转移，发现只要枚举中间点
x
x
x ，让
[
l
,
x
]
[l,x]
[l,x] 合成前
s
−
1
s-1
s−1 位，
(
x
,
r
]
(x,r]
(x,r] 合成最后一位即可
注意当
s
s
s 的长度为
0
0
0 时，将其变为
k
k
k 即可
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std
;
const int N
=305;
int n
,k
,a
[N
],b
[N
],c
[N
];
LL f
[N
][N
][N
],ans
=-2e18;
char s
[N
];
int main(){
scanf("%d%d%s",&n
,&k
,s
+1);
for (int i
=1;i
<=n
;i
++) c
[i
]=s
[i
]^48;
for (int i
=0;i
<(1<<k
);i
++)
scanf("%d%d",&a
[i
],&b
[i
]);
for (int i
=1;i
<=n
;i
++)
for (int j
=1;j
<=n
;j
++)
for (int l
=0;l
<(1<<k
);l
++)
f
[i
][j
][l
]=-2e18;
for (int i
=1;i
<=n
;i
++) f
[i
][i
][c
[i
]]=0;
for (int len
=1;len
<n
;len
++){
for (int r
,v
,l
=1;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]);
}
}
}
for (int i
=0;i
<(1<<k
);i
++)
ans
=max(ans
,f
[1][n
][i
]);
return printf("%lld\n",ans
),0;
}
