佛山网站建设哪儿有,服务器一年多少钱,广州做seo的公司,网站开发设计是前端吗update in 2019.1.21 优化了一下文中年代久远的代码 的格式…… 什么是决策单调性#xff1f; 在满足决策单调性的情况下#xff0c;通常决策点会形如1111112222224444445555588888..... 即不可能会出现后面点的决策点小于前面点的决策点这种情况。 那么这个性质应该如何使用…update in 2019.1.21 优化了一下文中年代久远的代码 的格式…… 什么是决策单调性 在满足决策单调性的情况下通常决策点会形如1111112222224444445555588888..... 即不可能会出现后面点的决策点小于前面点的决策点这种情况。 那么这个性质应该如何使用呢 1二分。 考虑到决策点单调递增因此我们考虑用单调队列存下当前的决策选取情况。 单调队列中存的量会带3个信息这是哪个决策点这个决策点会给哪个区间的点产生贡献这是一个区间所以算2个信息 相当于队列中存了很多个区间假设当前的决策点是这样的1111112222222333333 现在插入4这个决策那么我们就是要找到最靠左的合法位置将决策序列变为类似这样的序列111111222222444444444, 因为决策单调所以要覆盖肯定是一整段一整段的覆盖因此我们先判断4是否可以覆盖完3这个区间只需要看3的左端点是否可以被替换即可。 我们重复覆盖整个区间这个操作直到有个区间无法被完整覆盖或者已经到了不合法的位置(因为第x个点只能给区间[x 1, n]内的点产生贡献)。 如果这个区间无法被完整覆盖那么我们就在这个区间内二分找到最靠左的点使得4可以替换掉这个区间内的数然后修改管理这个区间的数的区间把被覆盖的区间让给4. 每次操作前弹掉已经没有用的决策点于是可以实现O(1)转移。(例如当前队首的决策点可以更新[3, x-1]这个区间但我们已经枚举到x了所以这个决策点显然就没有什么用了) 以下是某个年代久远的一道决策单调性优化的代码。 1 /*[NOI2009]诗人小G by ww3113306*/2 #includebits/stdc.h3 using namespace std;4 #define R register int5 #define AC 1001006 #define LL long long7 #define LD long double8 #define ac 1010009 #define inf 1000000000000000000LL
10 int t, L, p, n;
11 int Next[AC], s[AC], last[AC], l[AC], r[AC];//对应决策的管理区间,Next对last进行相反操作,以便输出
12 int q[AC], head, tail;//存下当前是哪个决策
13 LD f[AC];
14 LL sum[AC];
15 char ss[ac][45];
16
17 inline LD qpow(LD x)//error!!!x也要用LD
18 {
19 LD ans 1;int have p;
20 while(have)
21 {
22 if(have 1) ans * x;
23 x * x, have 1;
24 }
25 return ans;
26 }
27
28 inline LD count(int x, int j){return f[j] qpow(abs(sum[x] - sum[j] - L - 1));}//j --- x
29
30 inline void pre()
31 {
32 scanf(%d%d%d, n, L, p);
33 for(R i 1; i n; i )
34 {
35 scanf(%s, ss[i] 1);
36 s[i] strlen(ss[i] 1) 1;//加上后面的空格
37 sum[i] sum[i-1] s[i];//求出前缀和
38 }
39 }
40
41 void half(int x)//二分查找
42 {
43 int now q[tail], ll max(l[now], x 1), rr n, mid;//因为可能可以覆盖多个区间
44 while(ll rr)
45 {
46 mid (ll rr) 1;
47 if(count(mid, x) count(mid, now)) rr mid;//如果更优就往左缩短
48 else ll mid 1;//不然就向右寻找
49 }
50 r[q[tail]] ll - 1;
51 q[tail] x, l[x] ll, r[x] n;
52 }
53
54 inline void getans()
55 {
56 head 1, tail 1, q[1] 0, l[0] 1, r[0] n;
57 for(R i 1; i n; i )
58 {
59 while(r[q[head]] i) head;//如果当前队首已经取不到了
60 int now q[head];
61 f[i] count(i, now);//error ??? 用函数的话会爆了会自动转换为inf?
62 last[i] now;
63 if(count(n, q[tail]) count(n, i)) continue;//如果最后一个都不够优那就不二分了
64 while(count(l[q[tail]], q[tail]) count(l[q[tail]], i)) --tail;//如果当前可以覆盖前面的整个区间
65 half(i);//注意上面的while要在调用half之前修改这样取到的now才是正确的
66 }
67 }
68
69 inline void write()
70 {
71 if(f[n] inf) puts(Too hard to arrange);
72 else
73 {
74 printf(%lld\n, (LL)(f[n] 0.5));//注意精度误差
75 for(R i n; i; i last[i]) Next[last[i]] i;
76 int now 0;
77 for(R i 1; i n; i )
78 {
79 now Next[now];//now先跳了吧
80 int be now;//先只到这行结尾因为for还要加的
81 for(R j i; j be; j ) printf(%s , ss[j] 1);
82 printf(%s\n, ss[be] 1), i be;//最后再赋i,因为for中还要用到当前i
83 }
84 }
85 puts(--------------------);
86 }
87
88 int main()
89 {
90 scanf(%d, t);
91 while(t--) pre(), getans(), write();
92 return 0;
93 } View Code 2分治 假设我们当前的被决策区间是[l, r], 决策点区间是[ll, rr],那么我们取被决策区间的中点mid (l r) 1,然后在[ll, rr]中暴力寻找mid的最优决策点k于是根据决策单调性我们有 被决策区间[l, mid - 1]对应的决策点区间是[ll, k].同理被决策区间[mid 1, r]对应的决策点区间是[k, rr],于是我们就将这个区间划分为了2半不断向下递归减小决策点范围即可用正确的复杂度求出所有的转移。 转载于:https://www.cnblogs.com/ww3113306/p/9889295.html
