題解 假人

​​傳送門​​

像我這樣的小蒟蒻并不能在沒有std的情況下做出此題，不管是從思路上還是從代碼實作上

• 對于一類形如 \(f_{i, j}=\max\limits_{1\leqslant p\leqslant min(k_i, j)}f_{i-1, j-p}+a_{i, p}\)，且保證 \(a_{i, p}\) 随 \(p\) 單調不升/降問題的解法：

  發現隻考慮 \(i\) 本身的貢獻時dp值是凸的（此時就是 \(a_{i, p}\)）

  然後發現 \(i\) 和 \(i-1\) 間其實是獨立的（因為 \(p\) 與 \(j\) 無關，可以了解為把 \(j\) 拆成幾個 \(p\) 配置設定給不同的 \(i\)）

  于是可以分治，令 \(f_{l, r, j}\) 為給 \([l, r]\) 配置設定了 \(j\) 的最大貢獻

  合并的話因為原來的轉移實際上是一個不斷取max的過程，決策點形成一個凸包

  可以貪心地按每個凸包上兩個決策點之間的增量歸并排序

  這個東西實際上是兩個點集的闵可夫斯基和，這裡的點集是原凸包

  實際意義的話，大概可以了解為原凸包做闵可夫斯基和得到的圖形的邊界是原DP所有合并的極值

  是以新凸包的邊界上的點就是新的決策點了

回到這個題，發現 \(a_{i, p}\) 沒有凸性，是以 \(f_{i, i, j}\) 也沒有凸性，是以無法直接分治

但是神仙題解有神仙切入點……

于是可以按餘數分組合并了

複雜度 \(O(nk^2\frac{n}{k}logn)=O(nklogn)\)

然後代碼實作上有個花了我巨久的細節：這題把範圍從 \([1, 5]\) 調到了 \([0, 4]\)，而我在凸包上維護長度的時候還在設法讓下标從1開始

于是呢？炸，炸大個的

然後回來考慮一下題解切入用的結論

還有沒有類似的滿足 \(sum=2*k\)，則一定能拆出 \(sum=k\) 的子集的數呢？見dalao部落格

跟std基本一樣的 Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
#define pb push_back
#define int long long

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}

int n;
int siz[N], len[N];
ll a[N][6];

namespace task1{
ll dp[1010][5010];
void solve() {
int sum=0;
for (int i=1; i<=n; ++i) {
for (int j=i-1; j<=sum; ++j) {
for (int k=1; k<=siz[i]; ++k) {
dp[i][j+k]=max(dp[i][j+k], dp[i-1][j]+a[i][k]);
        }
      }
sum+=siz[i];
    }
for (int i=n; i<=sum; ++i) printf("%lld ", dp[n][i]);
printf("\n");
exit(0);
  }
}

namespace task2{
priority_queue<ll> q;
void solve() {
ll ans=0;
for (int i=1; i<=n; ++i) {
if (siz[i]==2) q.push(a[i][2]-a[i][1]);
ans+=a[i][1];
    }
printf("%lld ", ans);
while (q.size()) {
ans+=q.top(); q.pop();
printf("%lld ", ans);
    }
printf("\n");
exit(0);
  }
}

namespace task{
struct dat{
vector<int> v[12];
inline vector<int>& operator [] (int t) {return v[t];}
void put() {
cout<<"---dat---"<<endl;
for (int i=0; i<12; ++i) {cout<<i<<": "; for (auto it:v[i]) cout<<it<<' '; cout<<endl;}
    }
  };
void merge(dat& a, dat& b, dat& ans) {
cout<<"merge: "<<endl;
a.put(); b.put(); ans.put();
for (int i=0; i<12; ++i) if (a[i].size()) {
for (int j=0; j<12; ++j) if (b[j].size()) {
int dlt=(i+j>=12), k=(i+j)%12, x=0, y=0;
while (1) {
ans[k][x+y+dlt]=max(ans[k][x+y+dlt], a[i][x]+b[j][y]);
if (x==a[i].size()-1 && y==b[j].size()-1) break;
else if (x==a[i].size()-1) ++y;
else if (y==b[j].size()-1) ++x;
else ++((a[i][x+1]-a[i][x]>b[j][y+1]-b[j][y])?x:y);
        }
      }
    }
cout<<"return: "<<endl;
ans.put();
  }
dat solve(int l, int r) {
// cout<<"solve: "<<l<<' '<<r<<endl;
dat ans;
if (l==r) {
for (int i=1; i<=siz[l]; ++i) ans[(i-1)%12].pb(a[l][i]);
return ans;
    }
int tem=len[r]-len[l-1], mid=(l+r)>>1;
// for (int i=0; i<tem+r-l; ++i) ans[i%12].pb(-1);
for (int i=0; i<12; ++i)
for (int j=i; j<=tem; j+=12) ans[i].pb(-1);
dat a=solve(l, mid), b=solve(mid+1, r);
merge(a, b, ans);
return ans;
  }
void enter() {
dat ans=solve(1, n);
// cout<<"ans: "<<endl;
// ans.put();
for (int i=0; i<=len[n]; ++i) printf("%lld%c", ans[i%12][i/12], " \n"[i==len[n]]);
exit(0);
  }
}

signed main()
{
freopen("fake.in", "r", stdin);
freopen("fake.out", "w", stdout);

n=read();
bool all_one=1, leq2=1;
for (int i=1; i<=n; ++i) {
siz[i]=read();
len[i]=len[i-1]+siz[i]-1;
if (siz[i]!=1) all_one=0;
if (siz[i]>2) leq2=0; 
for (int j=1; j<=siz[i]; ++j) a[i][j]=read();
  }
// if (all_one || leq2) task2::solve();
// else task1::solve();
task::enter();

return 0;
}