| Time Limit: 2000MS | Memory Limit: 131072K | |
| Total Submissions: 15419 | Accepted: 4735 |
Description
Given an integer sequence { an } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.
Input
The first line of input contains two integer N (0 < N ≤ 100 000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.
Output
Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.
Sample Input
8 17 2 2 2 8 1 8 2 1
Sample Output
12
Hint
Use 64-bit integer type to hold M.
Source
朴素的方程非常简单
f[i]=max(f[j]+max(a[k])) (sum(a[k])<=M,i<=k<=j)
数据结构没法优化
只能够加速求max和sum，这个很简单，很基础，但是对决策和转移没有明显的优化
O（n^2）的复杂度没变
看看有没有没必要的转移
好像有一个贪心
就是每一段都要尽可能的取满
这是有误的，样例就是反例
那就是要么尽可能装满，要么尽可能装大的
“装大的”这个具体的式子怎么写?
好像明白了，1 8 1 8 2 2 2，然后m=17
尽可能装大的其实是尽可能不往小的里面塞大的
现在要做的就是维护只含这两种转移的决策集合
链表+二分好像可以，还是O（n^2）,主要是塞大的这个转移不好搞
这个最大值取的区间好像是单调移动的
可以单调队列？
很像，但不完全是吧
这个单调队列的队头不是最优决策，全部枚举一遍相当于没优化
那就再套一个数据结构吧
每次可以取出我们要的最优决策，盲猜logn复杂度
总体O(nlogn)
事实上我两个都写了，然后很妙，O(n^2)172ms,O(nlogn)972ms
这可是1000000啊
#include <iostream> #include <stdio.h> #include <algorithm> #include <cmath> #include <math.h> #include <string.h> #include <set> #define ll long long using namespace std; inline ll read() { char c=getchar();ll a=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b; } int n;ll m;int f[1000001],a[1000001];ll pre[1000001]; int que[1000001],head,tail; multiset<int> pq; int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++) { a[i]=read(); pre[i]=pre[i-1]+a[i]; if(a[i]>m) { cout<<"-1"<<endl; return 0; } } head=1,tail=0; int nw=1; // multiset<ll> pq; for(int i=1;i<=n;i++) { while(pre[i]-pre[nw-1]>m)nw++; while(head<=tail&&a[que[tail]]<a[i]) { if(head<tail) pq.erase(f[que[tail-1]]+a[que[tail]]);//Èç¹ûÊÇ×îºóÒ»¸ö£¬ÕÒ²»µ½Õâ¸öf+aµÄÖµ£¬¶øÇÒ×îºóÒ»¸öÆäʵÊÇûÓÐÒâÒåµÄ tail--; } que[++tail]=i; if(head<tail)pq.insert(f[que[tail-1]]+a[i]);//¸Õ¸Õ²åÈëµÚÒ»¸ö£¬Ã»ÓеڶþÖÖתÒÆ£¬¶¼ÊǵÚÒ»ÖÖ while(head<=tail&&que[head]<nw) { if(head!=tail)pq.erase(f[que[head]]+a[que[head+1]]); head++; } f[i]=f[nw-1]+a[que[head]];//µÚÒ»ÖÖתÒÆ if(head<tail)f[i]=min(f[i],*pq.begin()); } cout<<f[n]<<endl; return 0; }
#include <iostream> #include <stdio.h> #include <algorithm> #include <cmath> #include <math.h> #include <string.h> #include <set> #define ll long long using namespace std; inline ll read() { char c=getchar();ll a=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b; } int n;ll m;int f[1000001],a[1000001];ll pre[1000001]; int que[1000001],head,tail; multiset<int> pq; int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++) { a[i]=read(); pre[i]=pre[i-1]+a[i]; if(a[i]>m) { cout<<"-1"<<endl; return 0; } } head=1,tail=0; int nw=1; // multiset<ll> pq; for(int i=1;i<=n;i++) { while(pre[i]-pre[nw-1]>m)nw++; while(head<=tail&&a[que[tail]]<a[i]) { tail--; } que[++tail]=i; while(head<=tail&&que[head]<nw) { head++; } f[i]=f[nw-1]+a[que[head]];//µÚÒ»ÖÖתÒÆ for(int j=head;j<tail;j++) { f[i]=min(f[que[j]]+a[que[j+1]],f[i]); } // pq.insert(f[que[tail]-1]+a[que[tail]]); } cout<<f[n]<<endl; return 0; }
单调队列好像是只要取的是最大值就可以了
存活能力这个比喻真的算是说出了本质了
单调队列可以在满足无数个条件的情况下取出最优的最值
唯一的限制就是，某一个状态一旦不再满足其中一个条件，那它就再也不会满足这个条件了
这是保证了决策区间的单调移动
毕竟是O（1）的优化，限制大点没问题。。
这个单调队列更加的广义吧
里面不在是最优的决策集合，而是可以使用的决策集合
这个因为单调性可能只是体现在可能的决策集
这种优化只需满足上面说的一种限制：某一个状态一旦不再满足其中一个条件，那它就再也不会满足这个条件了
而之前的那种O（1）的优化则需要满足再这种情况下，位置越前的决策是越优秀的
似乎可以更加的扩展？
为了方便使用队列即使的删除掉不可用的决策，我们的队列必须要按照“生存能力”排序，也就是队头处的决策总是会先离开合法范围
那如果我们的条件多了呢？
那不就不一定从队头弹出了
那我们需要一个能够按照某个顺序（也就是要求）快速查找我们需要的元素，并且支持动态的删除和添加元素
平衡树。。
平衡树优化dp。。。
想想都难绷啊
但是其实这种题目是强套的，就是解构过后，知道平衡树的人是能够直接写出来的
这种东西也有限制，因为大概率对于不同的限制，顺序并不会按照同一个，也就是查找可能并不通用
能够转换排序关键字的平衡树。。如果转换的关键字没有联系，那就是O（nlogn）
所以如果这个关键字有联系
那就可以转换了？可以的，我会出黑题了
草
我发现我现在写dp方程都不想想贪心的可能的
太快了，应该多思考一下再想想dp的可能，根本就没去排除贪心