1D1D 动态规划的转移式是长这样的:
对于形如 f(i)=min(f(j)+w(j,i)) ,1<=i<=n-1f(i)=min(f(j)+w(j,i)),1<=i<=n?1 的状态转移方程, 记 p[i]p[i] 为令 f[i]f[i] 取到最小值的 jj 的值, 即 p[i]p[i] 是 f[i]f[i] 的最优决策. 若 pp 在 [1,N][1,N] 上单调不见, 则称 f 具有决策单调性
其中 w[i,x] 需要满足四边形不等式
emmm 四边形不等式是什么呢?
对于定义域上的任意整数 a,b,c,d, 其中 a\le b \le c \le da≤b≤c≤d
都有 w(a,d)+w(b,c)\ge w(a,c)+w(b,d)w(a,d)+w(b,c)≥w(a,c)+w(b,d) 成立, 则称函数 w 满足四边形不等式
(另一种定义)
对于定义域上的任意整数 a,b, 其中 a<ba<b
都有 w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)w(a,b+1)+w(a+1,b)≥w(a,b)+w(a+1,b+1) 成立, 则称函数 w 满足四边形不等式
至于证明 (我才高一我不会很正常)
然后就可以进行 1D1D 动态规划啦!
1D1D 的本质 (我理解的本质) 就是现将所有决策点的决策值定为 1 然后以此加入 2 决策值, 3 决策值...... 每次加入决策值都可以通过二分来找决策点 通过判断当前二分的决策点是采用新加入的决策值更优还是之前的方案更优
关于栈.. 其实我觉得这种更像是 (单调) 队列 因为我们总是保证 q[head] 是最优解
在实现时我们使用一个 qq 结构体, 存储 l,r,numl,r,num, 表示 num 决策点的起点与终点是 l,r
然后我们进行以下操作
1. 判断当前 q[head].r<iq[head].r<i 如果是的话, 就弹出队首, 因为当前决策点 i 至少都是从位置 i 开始进行决策的, 所以当前队首对当前决策点没有影响, 后面也没有影响, 应该弹出.
2. 判断当前的 calc(i,n)<=calc(q[tail].p,n)calc(i,n)<=calc(q[tail].p,n) 如果是的话, 表明当前的决策比队尾要优秀, 应当判断当前决策点的范围以及终点
3. 如果 calc(q[tail].p,q[tail].l)>=calc(i,q[tail].l)calc(q[tail].p,q[tail].l)>=calc(i,q[tail].l) 表明当前决策点比队尾优秀, 队尾弹出
4. 否则说明决策点在当前队尾的范围内, 需要通过二分查找
5. 加入新的决策点 i (真是不容易啊)
那么终于我可以上代码啦
- #include
- #include
- #include
- #include
- #include
- #include
- #define ld long double
- #define int long long
- using namespace std;
- const int maxn=500010;
- const ld MAX=1e18;
- struct node{
- int l;int r;int num;
- }q[200010];
- int n,m,p,len,pr[maxn];
- ld sum[maxn];
- char ch[maxn][50];
- ld f[maxn];
- ld pow(ld b){
- if(b<=0) b=-b;
- ld a=1;
- for(int i=1;i<=p;i++)
- a*=b;
- return a;
- }
- ld calc(int x,int y)
- {
- return f[x]+pow(sum[y]-sum[x]+y-x-1-m);// 此处 y-x-1 是因为如果两句话合并在一行, 会有空格 需要占据一个长度
- }
- int find(node t,int x)
- {
- int l=t.l,r=t.r;
- while(l<=r)
- {
- int mid=(l+r)>>1;
- if (calc(x,mid)<=calc(t.num,mid)) r=mid-1;
- else l=mid+1;
- }
- return l;
- }
- void dp()
- {
- int head=1,tail=0;
- q[++tail]=(node){0,n,0};
- for(int i=1;i<=n;i++)//i 代表的当前的决策为 i
- {
- if(q[head].r<i && head<=tail)// 这里如果队头的右端点小于 i, 因为这个状态对当前状态没有影响
- head++;
- f[i]=calc(q[head].num,i);
- pr[i]=q[head].num;
- if(calc(i,n)<=calc(q[tail].num,n))
- {
- while(head<=tail&&calc(q[tail].num,q[tail].l)>=calc(i,q[tail].l)) tail--;// 对于 f[lt] 来说, i 比 jt 更优
- // 注意此处是与 tail 的左端点进行比较, 因为左端点才能决定是否更优
- // 如果新决策点更优 则说明队尾全部都不如新决策点
- // 如果新决策点在左端点不是更优, 说明了新决策点的左端点在 tail 的 l,r 之内
- if(head>tail)q[++tail]=(node){i,n,i}; // 如果队列空了, 说明当前决策点优于所有队列中的点, 直接入队
- else{
- int x=find(q[tail],i);
- q[tail].r=x-1;
- q[++tail]=(node){x,n,i};
- }
- }
- }
- }
- signed main()
- {
- int t;scanf("%lld",&t);
- while(t--)
- {
- cin>> n>> m>> p;
- for(int i=1;i<=n;i++)
- {
- scanf("%s",ch[i]);
- len=strlen(ch[i]);
- sum[i]=sum[i-1]+len;
- }
- dp();
- if(f[(int)n]>MAX)
- {
- puts("Too hard to arrange");
- printf("--------------------\n");
- }
- else
- {
- printf("%lld\n",(long long)f[(int)n]);
- //printf("%.0f\n",(double)f[(int)n]);//long double 转成 double 输出
- int t,i;
- for(q[t=0].num=i=n;i;q[++t].num=i=pr[i]);
- for(;t;--t){
- for(i=q[t].num+1;i<q[t-1].num;++i)
- printf("%s",ch[i]);
- puts(ch[i]);
- }printf("--------------------\n");
- }
- }
- }
总结, 1D1D 动态规划是一种非常好的算法, 而且如果找出了这道题的 dp 式, 并且满足决策点单调递增的, 并且 w(j,i)w(j,i) 满足四边形不等式 那么我们就可以愉快的使用 1D1D 啦!
(悄悄说一句, 基本上所有的 1D1D 动态规划的打法都是一样的, 只有 calccalc 函数不太一样)
还有一个附加知识点, 就是 longlong doubledouble 函数的输出可以转换为 long long 形式或者 double 形式.
(又悄悄说一句, 这道题和玩具装箱一摸一样, 这道题的空格相当于玩具之间的填装物, 句子的长度相当于玩具的长度, 还有常数也是相同的意义. 所以唯一的区别就是一个需要输出方案, 一个不需要输出方案)
来源: http://www.bubuko.com/infodetail-3234427.html