一开始想的贪心，可是发现贪心的问题太多了啊！只能保证当前最优，全局完全无法考虑。
所以正解是dp。预处理出前缀和，枚举每个区间，在每个点记录$now[i]$表示以$i$这个塔结尾的塔组目前的高度。$dp[i]$表示以$i$这个塔结尾最多能分成多少组。如果$dp[i]$可以更新成更优值，则直接更新$dp$和$now$值，否则如果$dp$值相同，则尽量使$now$值最小。
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std; ll n, h[], pre[], now[], dp[]; int main ( ) {
freopen ( "tower.in", "r", stdin );
freopen ( "tower.out", "w", stdout );
scanf ( "%I64d", &n );
for ( int i = ; i <= n; i ++ )
scanf ( "%I64d", &h[i] ), pre[i] = pre[i-] + h[i];
for ( int i = ; i <= n; i ++ )
for ( int j = ; j < i; j ++ ) {
if ( pre[i] - pre[j] >= now[j] ) {
if ( dp[i] < dp[j] + ) dp[i] = dp[j] + , now[i] = pre[i] - pre[j];
else if ( dp[i] == dp[j] + ) {
now[i] = min ( now[i], pre[i] - pre[j] );
}
}
}
printf ( "%I64d", n - dp[n] );
return ;
}
显然（？）也是dp，$dp[i][j]$表示完成了$i$天，此时能力值为$j$时能做的最多工作量。$fine[i]$是预处理出的能力值为$i$时的效率最高的工作需要的时间。$qwq[i][j]$表示每个上完课后的第1天$i$，能力值为$j$，上课最短的时间。$pre[i]$表示过了$i$天可以得到的最大$dp$值。
枚举天数，能力值。
每次更新时可以选择不作为，即$dp[i][j]$直接从$dp[i-1][j]$转移过来。
如果第$i$天是某次刚上完课的第二天，则可以选择上课，从上课开始之前的最优$dp$值转移过来，即上课开始那一天的$pre$值。
如果当前天数和$fine[j]$满足可以工作，则从不工作那天转移过来，可以选择工作一次。
【注意】$dp$值初始化是负无穷，保证如果第$i$天不能满足$j$的能力值，则一定不会被更新，或去更新$pre$值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
using namespace std; int T, S, N, fine[], qwq[][], pre[], dp[][]; struct LRN {
int m, l, a;
} stdy[]; int main ( ) {
freopen ( "wrk.in", "r", stdin );
freopen ( "wrk.out", "w", stdout );
scanf ( "%d%d%d", &T, &S, &N );
memset ( qwq, 0x3f3f3f3f, sizeof ( qwq ) );
for ( RG int i = ; i <= S; i ++ ) {
int m, l, a;
scanf ( "%d%d%d", &m, &l, &a );
qwq[l+m][a] = min ( qwq[l+m][a], l );
}
memset ( fine, 0x3f3f3f3f, sizeof ( fine ) );
for ( RG int i = ; i <= N; i ++ ) {
int c, d;
scanf ( "%d%d", &c, &d );
fine[c] = min ( fine[c], d );
}
for ( int i = ; i <= ; i ++ )
fine[i] = min ( fine[i], fine[i-] );
memset ( dp, -0x3f3f3f3f, sizeof ( dp ) );
dp[][] = ;
for ( int i = ; i <= T; i ++ ) {
for ( int j = ; j <= ; j ++ ) {
dp[i][j] = dp[i-][j];
if ( qwq[i][j] != 0x3f3f3f3f ) dp[i][j] = max ( dp[i][j], pre[i-qwq[i][j]] );
if ( i - fine[j] >= ) dp[i][j] = max ( dp[i][j], dp[i-fine[j]][j] + );
pre[i] = max ( dp[i][j], pre[i] );
}
}
printf ( "%d", pre[T] );
return ;
}
很有趣的一道题。题目给出的性质是只有一个点的度数大于等于3，先找出这个点作为root。
bfs预处理出点距离的邻接矩阵，二分答案，每次去check的时候是选择root周围可以覆盖它的点，割掉这个点去更新答案。设当前枚举的点是$x$，先标记$x$可以覆盖的所有点，再dfs去计算没有被标记的点的数量，就是被拆分开的一条条链上的点的数量，每条链上需要的树洞是$ceil ( \frac{1.0 * now}{2*len+1} )$，$now$是这条链上的点数，注意因为自己也会算进去，所以一个点能覆盖的点数是$2*len+1$。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std; int n, m, k, root;
int dis[][], d[]; int stot, tov[], nex[], h[];
void add ( int u, int v ) {
tov[++stot] = v;
nex[stot] = h[u];
h[u] = stot;
} queue < int > q;
void bfs ( int s ) {
queue < int > q; q.push ( s );
while ( !q.empty ( ) ) {
int x = q.front ( ); q.pop ( );
for ( int i = h[x]; i; i = nex[i] ) {
int v = tov[i]; d[x] ++; d[v] ++;
if ( !dis[s][v] && v != s )
dis[s][v] = dis[s][x] + , q.push ( v );
}
}
} int now, v[]; void dfs ( int u ) {
now += ( v[u] = );
for ( int i = h[u]; i; i = nex[i] )
if ( !v[tov[i]] )
dfs ( tov[i] );
} int work ( int x, int len ) {
int s = ;
memset ( v, , sizeof ( v ) );
for ( int i = ; i <= n; i ++ )
v[i] = ( dis[i][x] <= len );
for ( int i = ; i <= n; i ++ )
if ( !v[i] ) now = , dfs ( i ), s += ceil ( 1.0 * now / ( * len + ) );
return s;
} bool check ( int x ) {
int ans = 0x3f3f3f3f;
for ( int i = ; i <= n; i ++ )
if ( dis[root][i] <= x ) {
ans = min ( ans, work ( i, x ) );
}
return ans < k;
} int main ( ) {
freopen ( "holes.in", "r", stdin );
freopen ( "holes.out", "w", stdout );
scanf ( "%d%d%d", &n, &m, &k );
for ( int i = ; i <= m; i ++ ) {
int x, y;
scanf ( "%d%d", &x, &y );
add ( x, y ); add ( y, x );
}
for ( int i = ; i <= n; i ++ ) {
bfs ( i );
if ( d[i] > ) root = i;
}
if ( !root ) {
cout << ceil ( 1.0 * ( n - k ) / ( k << ) );
return ;
}
int l = , r = n, ans;
while ( l <= r ) {
int mid = ( l + r ) >> ;
if ( check ( mid ) ) r = mid - , ans = mid;
else l = mid + ;
}
cout << ans;
return ;
}