Problem

https://www.luogu.org/problemnew/show/P2157

Solution

一开始是想做二维，即第二维状态压缩。
然后考虑转移，那么再枚举一个最优打饭的顺序。
但这样的话，第一个打饭的人和前一个打饭的人不知道呀？多加一维记录前一个打饭的人么？
太麻烦了吧..

最后确实要多加一维，同时可以把多出来的那一维省去。

我也不知道我在干什么... 被那个 ok 函数的含义卡了好久..

一开始是完全错的，然后后来又改成了半对半错——正确的应该是若 $i$ 没打饭，那么才有 $(i, i+b_i]$ 这个限制，否则是没有的...

我也不知道我干什么搞了一晚上才发现这个错误...

Code

// Code by ajcxsu
// Problem: food

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;

const int N=1001, T=1<<8, U=T-1;
int c[N], b[N];
int f[N][T][17];

bool ok(int i, int j, int x) {
    int k=0;
    while(x) {
        if(!(j&1) && x>b[i+k]) return false;
        k++, x--, j>>=1;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int cas;
    cin>>cas;
    while(cas--) {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>c[i]>>b[i], b[i]=min(b[i], n-i);
        CLR(f, 0x3f);
        f[1][0][7]=0;
        int ans=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
            for(int j=1;j<T;j++)
                for(int k=0;k<=b[i]+8;k++) {
                    if(k>=8 && (j&(1<<(k-8))) && ok(i, j^(1<<(k-8)), k-8))
                        for(int l=0;l<=b[i]+8;l++)
                            if(i+l-8>=0)
                                f[i][j][k]=min(f[i][j][k], f[i][j^(1<<(k-8))][l]+
                                (i+l-8?(c[i+k-8]^c[i+l-8]):0));
                    if(j&1) {
                        if(k && i!=n) f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1], f[i][j][k]);
                        if(i==n) ans=min(ans, f[i][j][k]);
                    }
                }
        printf("%d\n", ans);
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2157.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆