HAOI 2008 木棍分割

HAOI 2008 木棍分割

//需要优化很多的DP，包括预处理前缀和，滚动数组，预处理可转移状态 
#include<bits/stdc++.h>
using namespace std;
const int moder = 10007;
const int maxn = 50010;
const int inf = 0x3f3f3f3f;
int n, m, tmp;
int f[maxn], a[maxn], last[maxn], tot[maxn], sum[maxn];inline bool check(int mid){int tot = 0, final = 0;for(int i = 1; i <= n; i++){if(tot + a[i] <= mid)    tot += a[i];else if(a[i] <= mid)    tot = a[i], final++;else if(a[i] > mid)    return 0;if(final > m)    return 0;}if(final == m)    return 1;
}int main(){scanf("%d%d", &n, &m);int mina = inf;for(int i = 1; i <= n; i++){scanf("%d", &a[i]);mina = min(a[i], mina);sum[i] = sum[i-1] + a[i];}int ans;int l = mina, r = sum[n] + 1;while(l < r){int mid = l + r >> 1;if(check(mid)){ans = mid;r = mid;}else l = mid + 1;}//第一问二分 for(int i = 1; i <= n; i++){if(sum[i] <= ans)    f[i] = 1;//预处理ans从开始能到的状态 else break;}for(int i = 1; i <= n; i++)tot[i] = (tot[i-1] + f[i]) % moder;//预处理前缀和 int now = 0;for(int i = 1; i <= n; i++){while(1){if(sum[i] - sum[now] <= ans)    break;else now++;}last[i] = now-1;//找每个i符合条件的转移状态 }for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++)f[j] = (tot[j-1] - tot[last[j]] + moder) % moder;for(int j = 1; j <= n; j++)tot[j] = tot[j-1] + f[j];tmp = (tmp + f[n]) % moder;//至多m次，所以每次都转移 }printf("%d %dn", ans, tmp);return 0;
}