傳送門 第一問隨便二分就過了，此處略去。 第二問DP f[i][j]前i根木棍，砍了j刀的方案數(shù)。 轉(zhuǎn)移方程很顯然，此處略去。 我們可以滾掉一維。 但是轉(zhuǎn)移要O（n^2m），顯然要T 于是我們可以用單調(diào)隊(duì)列+前綴和優(yōu)化轉(zhuǎn)移，使得時(shí)間復(fù)雜度降為O（nm) 然后就過了。
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>using namespace std;int f[2][50005],a[50005];int n,m,x,l,r,mi,s,sum,c,k,ans;int main(){ scanf("%d%d",&n,&m); m++; for (int i=1;i<=n;i++){ scanf("%d",&x); a[i]=a[i-1]+x; if (x>l) l=x; } r=a[n]; while (l<r){ mi=(l+r)/2; s=1; sum=1; for (int i=1;i<=n;i++) if (a[i]-a[s-1]>mi){ sum++; s=i; } if (sum>m) l=mi+1; else r=mi; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
