广东住房和城乡建设局网站首页,制作微网站的费用,网站301重定向 权重转移,泉州seo代理计费正题 大意
每个人有两个值gigi和hihi#xff0c;要求将序列分解成连续的几个序列。要求每个序列最大的hihi的和小于Limt的情况下每个序列gigi的和的最大值最小。 解题思路
我们二分最小的gigi的和的最大值 首先一个O(n2)O(n2)的dp想法#xff0c;用fifi表示分割到第i个时最…正题 大意
每个人有两个值gigig_i和hihih_i要求将序列分解成连续的几个序列。要求每个序列最大的hihih_i的和小于Limt的情况下每个序列gigig_i的和的最大值最小。 解题思路
我们二分最小的gigig_i的和的最大值 首先一个O(n2)O(n2)O(n^2)的dp想法用fifif_i表示分割到第i个时最大的hihih_i的和的最小值。 动态转移
fimin{f[j]max{hj,hj1,hj2...hi−1,hi}}fimin{f[j]max{hj,hj1,hj2...hi−1,hi}}
f_i=min\{f[j]+max\{h_j,h_{j+1},h_{j+2}...h_{i-1},h_i\}\}我们考虑如何优化每次有新的max只会在产生更大的hihih_i时于是我们可以用一个nextinextinext_i表示最近的hnexthihnexthih_{next}>h_i然后我们可以二分快速找到满足小于你目前二分到的答案的最小的位置。 时间复杂度O(n2n (log n)2)O(n2n(logn)2)O(n^2+n\ \ (log\ n)^2) 是不是感觉时间复杂度没有变化巧了它就是A了 代码
#includecstdio
#includealgorithm
#includecstring
#define H 20010
#define ll long long
using namespace std;
int n,h[H],g[H],z[H],next[H],num[H],tot;
ll sum[H],L,f[H],ans,l,r;
int find(int x,int need)//二分满足条件的最小值
{int lx,rn;while(lr){int mi(lr)/2;if(sum[mi]-sum[x-1]need) rmi;else lmi1;}return l;
}
bool check(int x)
{memset(f,127/3,sizeof(f));f[1]0;for (int i1;in;i)//dp{int kfind(i,x),yi,addh[y];if (sum[k]-sum[i-1]x) k--;while(yk){f[y]min(f[y],f[i]add);addh[y];ynext[y];}f[k1]min(f[k1],f[i]add);}return f[n1]L;
}
int main()
{scanf(%d%lld,n,L);for(int i1;in;i){scanf(%d%d,h[i],g[i]);sum[i]sum[i-1]g[i];}num[1]n1;z[1]2147483647;tot1;for (int in;i;i--)//暴力next数组{while (z[tot]h[i]) tot--;next[i]num[tot];tot;num[tot]i;z[tot]h[i];} l1;rsum[n];ansr;while(lr)//二分{int mid(lr)1;if (check(mid)) {if (midans)ansmid;rmid-1;}else lmid1;}printf(%lld,ans);
}
