Solution

没切，可怕。

显然可以压缩后 \max\{x,y\} 位，做 O(n2^{\max\{x,y\}}) 的 \rm DP。

肯定过不去，矩阵快速幂优化也不行。

本题需要用到结论：一定可以由某个长度为 (x+y) 的 01 串通过循环得到最终的串。

证明是容易的。但是题解区的部分证明存在不严谨的地方。

如果长度为 x+y 的 01 串 A 是合法的，那么显然 AAA\cdots AAA 也是合法的，所以只用保证 A 合法就行了（本质是 -x \equiv y \pmod {x+y}）

固定前 (x+y) 个字符，组成串 A。如果 A 后 (x+y) 个字符组成的串和 A 不一样，记为 B，那么将 AB 换为 CC（其中 C 是 A 和 B 中 1 的个数较大者，相同随便选一个）显然不劣。因此前 (x+y) \lfloor \dfrac{n}{x+y} \rfloor 个字符应当都是有循环节的。

考虑剩余 n \bmod (x+y) 个字符，设为 D，A 可以写成 EF，其中 |D|=|E|。我们证明：存在最优解使得 D 中 1 的个数不比 E 多，这时候将 D 替换为 E。

反证，注意 FD 合法，所以最优的应该是 DF 而不是 EF，与假设矛盾。

所以可以对前 x+y 位做 \rm DP，复杂度 O((x+y)2^{x+y})。

本题的优化方法和普通题目有很大差异：提出了一个看起来相当强的结论，大规模缩减问题。需要很大的胆量做这种操作。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=50;
int n,x,y,mul[MAXN],dp[2][(1<<22)];
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>x>>y;
    if(x>y) swap(x,y);
    ffor(i,1,x+y) mul[i]=n/(x+y)+(i<=n%(x+y));
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0]=0;
    ffor(i,1,x+y) {
        int s=i&1;
        ffor(o,0,(1<<y)-1) dp[s][o]=-0x3f3f3f3f;
        ffor(o,0,(1<<y)-1) {
            if(!(o&1)&&!(o&(1<<y-x))) dp[s][(o>>1)|(1<<y-1)]=max(dp[s][(o>>1)|(1<<y-1)],dp[s^1][o]+mul[i]);
            dp[s][o>>1]=max(dp[s][o>>1],dp[s^1][o]);
        }
    }
    int mx=0;
    ffor(i,0,(1<<y)-1) mx=max(mx,dp[(x+y)&1][i]);
    cout<<mx;
    return 0;
}