题解 P3646 【[APIO2015]巴厘岛的雕塑】
本蒟蒻第一次水题解
希望管理员大大给过
今天刚好考了这题， 在考场上写了个朴素的DP，结果数据太水，得了80分，知道洛谷上有这题， 来试水，结果出乎意料，错误的DP竟然有90分（haha）， 下面是丑陋的代码：
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1), ch = getchar();
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
#define N 2005
#define ll long long
#define reg register
int n, A, B;
ll f[N][N];
ll ans = 0, res = 0;
int main(){
//freopen("sculpture.in", "r", stdin);
//freopen("sculpture.out", "w", stdout);
n = read(), A = read(), B = read();
for(reg int i = 0; i <= n; i++){
for(reg int j = 0; j <= B; j++)
f[i][j] = 9999999999999;
}
f[0][1] = 0;
for(reg int i = 1; i <= n; i++)
f[i][1] = (ll)(read() + f[i - 1][1]);
for(reg int i = 1; i <= n; i++)
for(reg int k = 2; k <= min(i, B); k++)
for(reg int j = i - 1; j >= 1; j--)
if(f[i][1] - f[j][1] > f[i][k])break;//玄学剪枝，O(n^3) 超时不存在的
else f[i][k] = min(f[i][k], f[j][k - 1] | (f[i][1] - f[j][1]));
ll ans = 9999999999999;
for(reg int i = A; i <= B; i++){
ans = min(f[n][i], ans);
}
printf("%lld", ans);
return 0;
}为什么错？ 因为前一个分段的最小优美值与后一个分段的值或运算起来不一定是最小的答案，这个可以自己思考一下。
那咋搞， 本蒟蒻自己当然想不出。听大佬说是数位DP，本蒟蒻当然不会，自己马上查了资料，借鉴Cao某的代码和Only_xiaohuang的解释，终于打出了这题，自己想的成分（0%）；
正片
所谓数位DP就是逐个数位考虑，一般运用于二进制运算这样的题。不太懂得自行百度。
先看到这个题，很显然我们要找到一个解使得二进制高位上的数为0。我们就可以从高位到低位逐位考虑这一位是否为0的情况。我们令分bool f[i][j] 前i个数分成j段的当前数位能否为0，能为0则为true， 不能则为false； 那么我们每枚举一个数位就要DP一次，第一层循环代码如下
#define ll long long
#define N 2005
bool f[N][N];
ll solve1(){
ll ans = 0, res = 0;
int maxn = log2(sum) + 1;//sum为每一个Y的和，这是确定枚举的最高位
for(int i = maxn; i >= 0; i--){
res = ans | ((1LL << i) - 1LL);
memset(f, false, sizeof(f));//每次枚举都要清空
f[0][0] = true;//初始值
.
.
.
bool flag = false;
for(int j = A; j <= B; j++){//枚举分A到B段的所有情况
if(f[n][j]){
flag = true;
break;
}
}
if(!flag)ans |= (1LL << i);//不可以放0则只能放1
}
return ans;
}那么res，ans分别是什么呢？ ans比较好理解，假如当前枚举的数位不能放0，那就把ans二进制下的第i位改为1，最后得到的ans值就是最后的答案。 那么res呢，这里是仿照Cao某的方法，假如ans（二进制） = 1101 0000，枚举到第四位，那么res = 1101 0111，也就是把第四位扣下来，再把后面每一位附为1，这里就是假设这一位为0，这样做是为了下面的状态转移。 那么最重要的来了，f数组的状态转移：
for(int j = 1; j <= n; j++){//枚举第几个数
for(int k = 1; k <= min(j, B); k++){//分段数
ll s = 0;
for(int t = j - 1; t >= k - 1; t--){//枚举分段位置
s += d[t + 1];//s表示t+1~j的Y的和
if(f[t][k - 1] && ((s | res) == res)){
f[j][k] = true;
break;
}
}
}
}为什么(f[t][k - 1] && ((s | res) == res))成立，则f[j][k]便可以为真？； (s | res) == res 表示s二进制上的每一个1的位置，在res上也为1，那么当前面一段的值 或 上s时并不会影响之前的答案，且当前枚举的数位上可以为0，那么只要f[t][k - 1],也就是1~t中分k - 1段这一位上可以为0，那么f[j][k]的这一位上也能为0； 那就很简单了，完整代码如下
#define ll long long
#define N 2005
bool f[N][N];
ll solve1(){
ll ans = 0, res = 0;
int maxn = log2(sum) + 1;//sum为每一个Y的和，这是确定枚举的最高位
for(int i = maxn; i >= 0; i--){
res = ans | ((1LL << i) - 1LL);
memset(f, false, sizeof(f));//每次枚举都要清空
f[0][0] = true;//初始值
for(int j = 1; j <= n; j++){//枚举第几个数
for(int k = 1; k <= min(j, B); k++){//分段数
ll s = 0;
for(int t = j - 1; t >= k - 1; t--){//枚举分段位置
s += d[t + 1];//s表示t+1~j的Y的和
if(f[t][k - 1] && ((s | res) == res)){
f[j][k] = true;
break;
}
}
}
}
bool flag = false;
for(int j = A; j <= B; j++){//枚举分A到B段的所有情况
if(f[n][j]){
flag = true;
break;
}
}
if(!flag)ans |= (1LL << i);//不可以放0则只能放1
}
return ans;
}可是这样做只能得80分，原因是太慢了，四个for套在一起不超时才怪。 那怎么办，从数据入手，发现所有的大样例都有特殊性质，A = 1。 前面的代码是因为枚举了分段数，因为要保证正确的解分段数大于等于A， 防止最优解小于A，但A = 1的话就不需要考虑，只需保证最优解小于等于B就行了。 用g数组表示，前j个数分段使得当前数位为0所需的最小分段数， 很容易想到如何转移：
if((s | res) == res)
g[j] = min(g[j], g[k] + 1);完整代码与原函数类似：
ll solve2(){
ll ans = 0, res = 0;
int maxn = log2(sum) + 1;
for(int i = maxn; i >= 0; i--){
res = ans | ((1LL << i) - 1LL);
memset(g, 127, sizeof(g));
g[0] = 0;
for(int j = 1; j <= n; j++){
ll s = 0;
for(int k = j - 1; k >= 0; k--){
s += d[k + 1];
if((s | res) == res)
g[j] = min(g[j], g[k] + 1);
}
}
if(g[n] > B) ans |= (1LL << i);//如果得到0的最小分段数大于B，那么这一位只能为1
}
return ans;
}这道题就这样完美的解决了；
真完整代码如下
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1), ch = getchar();
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
#define N 2005
#define ll long long
int n, A, B, g[N];
ll d[N], sum;
bool f[N][N];
ll solve1(){
ll ans = 0, res = 0;
int maxn = log2(sum) + 1;//sum为每一个Y的和，这是确定枚举的最高位
for(int i = maxn; i >= 0; i--){
res = ans | ((1LL << i) - 1LL);
memset(f, false, sizeof(f));//每次枚举都要清空
f[0][0] = true;//初始值
for(int j = 1; j <= n; j++){//枚举第几个数
for(int k = 1; k <= min(j, B); k++){//枚举分段数
ll s = 0;
for(int t = j - 1; t >= k - 1; t--){//枚举分段位置
s += d[t + 1];//s表示t+1~j的Y的和
if(f[t][k - 1] && ((s | res) == res)){
f[j][k] = true;
break;
}
}
}
}
bool flag = false;
for(int j = A; j <= B; j++){//枚举分A到B段的所有情况
if(f[n][j]){
flag = true;
break;
}
}
if(!flag)ans |= (1LL << i);//不可以放0则只能放1
}
return ans;
}
ll solve2(){
ll ans = 0, res = 0;
int maxn = log2(sum) + 1;
for(int i = maxn; i >= 0; i--){
res = ans | ((1LL << i) - 1LL);
memset(g, 127, sizeof(g));
g[0] = 0;
for(int j = 1; j <= n; j++){
ll s = 0;
for(int k = j - 1; k >= 0; k--){
s += d[k + 1];
if((s | res) == res)
g[j] = min(g[j], g[k] + 1);
}
}
if(g[n] > B) ans |= (1LL << i);//如果得到0的最小分段数大于B，那么这一位只能为1
}
return ans;
}
int main(){
//freopen("sculpture.in", "r", stdin);
//freopen("sculpture.out", "w", stdout);
n = read(), A = read(), B = read();
for(int i = 1; i <= n; i++) d[i] = read(), sum += d[i];
if(A == 1) printf("%lld", solve2());
else printf("%lld", solve1());
return 0;
}
祝大家早日AC！！！