qoj8225 最小值之和 题解

题目链接

点击打开链接

题目解法

很牛的题啊

从 \(f\) 序列的最小值切入，考虑把 \(f_i:=f_i-f_{min}\)，会对 \(f'\) 造成什么影响？
发现会使 \(f'\) 中的每个数都减去 \((n-1)f_{min}\)，且会把原问题分成 \([1,min]\) 和 \([min+1,r]\) 这两个完全相同的子问题

于是考虑区间 \(dp\)，令 \(dp_{l,r,v}\) 表示当前操作 \([l,r]\) 这个区间，\(f'_i(l\le i\le r)\) 都减去了 \(v\)，是否可以构造出一组合法的 \(f\)
只要存在 \(dp_{l,k,v+q\times (r-l)}\) 和 \(dp_{k+1,r,v+q\times (r-l)}\) 都为 \(1\)，\(dp_{l,r,v}\) 就为 \(1\)

需要发现一个结论：如果 \(dp_{l,r,v}=1\)，则 \(dp_{l,r,v-(r-l)}=1\)，证明由转移方程可推得

根据这个结论，我们重新定义 \(g_{l,r,c}(0\le c<r-l)\) 表示对于所有 \(c\equiv v(\bmod r-l)\)，且 \(dp_{l,r,v}=1\) 的最大的 \(v\)
转移枚举 \(k\)，及左右的 \(c\)
我们需要找到最大的满足 \(x\equiv g_{l,k,c_1}(\bmod k-l)\) 且 \(x\equiv g_{k+1,r,c_2}(\bmod r-k-1)\)，且 \(x\le \min\{g_{l,k,c_1},g_{k+1,r,c_2}\}\) 的 \(x\)
然后一直往前跳 \(x\) 更新 \(g\)，知道出现 \(x\%(r-l)\) 相同的结束

时间复杂度 \(O(n^5)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=85;
int n,g[N],ans[N];
array<int,2> f[N][N][N];
void print(int l,int r,int v,int c1,int c2){
    auto [to,k]=f[l][r][v];
    ans[k]=(to-c1)/(r-l)+c2;
    if(l!=k) print(l,k,to%(k-l),to,ans[k]);
    if(k+1!=r) print(k+1,r,to%(r-k-1),to,ans[k]);
}
void upd(array<int,2> &ff,int x,int y){ if(x>ff[0]) ff[0]=x,ff[1]=y;}
int main(){
    read(n);
    F(i,1,n) read(g[i]);
    if(n==1){ puts(g[1]?"No":"Yes");exit(0);}
    ms(f,-1);
    F(i,1,n-1) if(g[i]==g[i+1]) f[i][i+1][0]={g[i],i};
    F(len,3,n) F(l,1,n-len+1){
        int r=l+len-1;
        if(f[l][r-1][g[r]%(r-1-l)][0]>=g[r]) upd(f[l][r][g[r]%(r-l)],g[r],r-1);
        if(f[l+1][r][g[l]%(r-1-l)][0]>=g[l]) upd(f[l][r][g[l]%(r-l)],g[l],l);
        F(k,l+1,r-2){
            int t=lcm(k-l,r-k-1);
            F(j,0,t-1){
                int p=min(f[l][k][j%(k-l)][0],f[k+1][r][j%(r-k-1)][0]);
                if(p==-1||p<j) continue;
                p=(p-j)/t*t+j;
                int st=p%(r-l);
                while(true){
                    upd(f[l][r][p%(r-l)],p,k);
                    p-=t;
                    if(p<0||p%(r-l)==st) break;
                }
            }
        }
    }
    if(f[1][n][0][0]==-1){ puts("No");exit(0);}
    print(1,n,0,0,0);
    puts("Yes");
    F(i,1,n-1) printf("%d ",ans[i]);puts("");
    return 0;
}