poj3017

題目大意：給一個長度為n的序列a，要你將其分成若干段，在滿足每段和不超過m的情況下，讓每段中的最大值之和最小，求最小值。

?

容易想到動態規劃，令f[i]表示把前i個數分段所得的最小值

f[i]=min{f[j]+max?_(j+1<=k<=i){a[k]}}?? ?（a[j+1]+a[j+2]+......+a[i]<=m）

時間復雜度o（n²），我們考慮如何優化。

考慮單調隊列，由于f[i]一定是單調不降的，

對于任意兩個連續決策j-1，j（0<=j-1<j<i且a[j+1]+a[j+2]+......+a[i]<=m）,我們分兩種情況：

情況1：若（a[j]+a[j+2]+......+a[i]>m）

? ? ? ? ? ? ??此時j-1不符合條件，j有用，優

情況2：若（a[j]+a[j+2]+......+a[i]<=m）

? ? ? ? ? ? ?當 存在? f[j-1]+max_(j<=k<=i){a[k]}? <=? ?f[j]+max_(j+1<=k<=i){a[k]}

? ? ? ? ? ? ?說明j-1更優，且隨著i的增大，j-1更容易滿足小于i，所以j為無用決策，應刪除。

? ? ? ? ? ? ?所以當且僅當? ? f[j-1]+max_(j<=k<=i){a[k]}? > f[j]+max_(j+1<=k<=i){a[k]}? ,j有用.

? ? ? ? ? ? ?因為f[j-1]<=f[j]

? ? ? ? ? ? ? 所以? ? max_(j<=k<=i){a[k]}? > max_(j+1<=k<=i){a[k]}

? ? ? ? ? ? ? 所以? ?a[j]=max_(j<=k<=i){a[k]}

綜上：若j更優，除了滿足（a[j+1]+a[j+2]+......+a[i]<=m）

? ? ? ? ? ?還應當滿足兩個條件之一

? ? ? ? ? ? ? ? 條件一? ?a[j]+a[j+2]+......+a[i]>m

? ? ? ? ? ? ? ?條件二? ?a[j]=max_(j<=k<=i){a[k]}

條件一容易處理，考慮條件二，維護一個決策點j單調遞增，a[j]單調遞減的隊列即可。

至于max?_(j+1<=k<=i){a[k]｝如何得到，其實就是隊列下一個元素的a值。

但注意到維護的隊列對f[j]+max?_(j+1<=k<=i){a[k]}沒有單調性，所以建立一個數據結構，如平衡樹set，存f[j]+max?_(j+1<=k<=i){a[k]}，

以便快速得到。（數據太水，直接暴力掃隊列竟然還要快一些）

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<set> 6 #define ll long long 7 using namespace std; 8 int f[100005],a[100005],q[100005]; 9 int n; 10 ll m,sum[100005]; 11 multiset<int> s; 12 int main() 13 { 14 int i,j; 15 scanf("%d%lld",&n,&m); 16 int L=1,r=0,k=0;//k為隊列區間起始位置L的前一個位置 (維護條件2) 17 for(i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]; 18 for(i=1;i<=n;i++) 19 { 20 if(a[i]>m){printf("-1");return 0;} 21 while(sum[i]-sum[k]>m)k++;//維護k 22 while(L<=r&&q[L]<=k) 23 { 24 if(L<r)s.erase(f[q[L]]+a[q[L+1]]);//刪去 區間和大于m的候選項 25 L++; 26 } 27 while(L<=r&&a[q[r]]<=a[i]) 28 { 29 if(L<r)s.erase(f[q[r-1]]+a[q[r]]);//維護a[]單調遞減 30 r--; 31 } 32 q[++r]=i; 33 if(L<r)s.insert(f[q[r-1]]+a[i]); 34 f[i]=f[k]+a[q[L]];//條件1更新f 35 if(L<r)f[i]=min(f[i],*s.begin());//條件2更新f 36 } 37 printf("%d",f[n]); 38 return 0; 39 }

?

轉載于:https://www.cnblogs.com/dsb-y/p/11008366.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Cut the Sequence（POJ3017）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。