dp學(xué)習(xí)筆記之P5124 Teamwork G
這是寫給我自己看的，以便復(fù)習(xí)。
[題目描述]
在 Farmer John 最喜歡的節(jié)日里，他想要給他的朋友們贈送一些禮物。由于他并不擅長包裝禮物，他想要獲得他的奶牛們的幫助。你可能能夠想到，奶牛們本身也不是很擅長包裝禮物，而 Farmer John 即將得到這一教訓(xùn)。Farmer John 的 N 頭奶牛\((1≤N≤10 ^4)\)排成一行，方便起見依次編號為 1…N。奶牛 i 的包裝禮物的技能水平為\(s_i\)。她們的技能水平可能參差不齊，所以 FJ 決定把她的奶牛們分成小組。每一組可以包含任意不超過 K 頭的連續(xù)的奶牛\((1≤K≤10^3)\)。并且一頭奶牛不能屬于多于一個小組。由于奶牛們會互相學(xué)習(xí)，這一組中每一頭奶牛的技能水平會變成這一組中水平最高的奶牛的技能水平。
請幫助 FJ 求出，在他合理地安排分組的情況下，可以達(dá)到的技能水平之和的最大值。
[題目解答]
點擊查看解答
很顯然這是一道線性dp題目，由于是區(qū)間最大值，我們就用st表（多寫寫，上了考場自有用處）。狀態(tài)轉(zhuǎn)移不難想，設(shè)\(f_i\)為前i個奶牛的最大技能水平，由此可知
\(f_i=max(f_i,f_{i-j}+getv(i-j+1,i))\)
接下來擼代碼就行了awa
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rgi register int
#define DEBUG(x) printf("%s ",x);
#define fastio cin.tie(nullptr)->ios::sync_with_stdio(false);
#define inf (1<<31)
#define awa {return 0;}
#define N 10010
using namespace std;
int n,k,a[N],dp[N],st[N][31],logn[100010];
void init(){
logn[1]=0,logn[2]=1;
for(rgi i=3;i<=100000;i++){
logn[i]=logn[i>>1]+1;
}
}
inline int getv(int l,int r){
int k=logn[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
fastio;
cin>>n>>k;
init();
for(rgi i=1;i<=n;i++){
cin>>a[i];
st[i][0]=a[i];
}
for(rgi j=1;j<=logn[n];j++){
for(rgi i=1;i+(1<<j)-1<=n;i++){
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
for(rgi i=1;i<=n;i++){
for(rgi j=1;j<=k;j++){
if(j>i)break;
// DEBUG("CHK");
dp[i]=max(dp[i],dp[i-j]+getv(i-j+1,i)*j);
}
}
printf("%d",dp[n]);
awa;
}
浙公網(wǎng)安備 33010602011771號