1563: [NOI2009]诗人小G

本文主要是介绍1563: [NOI2009]诗人小G，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

估计只有我这种蒟蒻才写了颗线段树吧…
容易找到n^2 dp方法：
即f[i] = min(|sum[i] - sum[j] - l + i - j - 1|^p)
然后令k > j且k优于j，简单思考得到…
若k当前已经优于j，那么以后一定会一直优于j
所以该方程满足决策单调…
那么考虑把当前点在哪个位置作为最优点，那么在这个点以后肯定一直是他最优（前提是原本这些位置上更优的点小于当前点）
所以二分判断即可…
c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
typedef long double ll;
using namespace std;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 1e5+500; const ll inf = 1e18;
int n,l,p,a[N],sum[N],fa[N];
char s[31];
long double f[N];struct segment_tree
{int sign[N << 3];inline void pre() { memset(sign,0,sizeof sign); }void put_down(int id){if(!sign[id]) return ;sign[id << 1] = sign[id];sign[id << 1 | 1] = sign[id];}int find(int id,int l,int r,int x){put_down(id);if(sign[id] || l == r) return sign[id];int mid = l + r >> 1;if(x <= mid) return find(id<<1,l,mid,x);else return find(id<<1|1,mid+1,r,x);}void modify(int id,int l,int r,int L,int R,int w){put_down(id); sign[id] = 0;if(l == L && R == r) return void(sign[id] = w);int mid = l + r >> 1;if(R <= mid) modify(id<<1,l,mid,L,R,w);if(L > mid) modify(id<<1|1,mid+1,r,L,R,w);else modify(id<<1,l,mid,L,mid,w),modify(id<<1|1,mid+1,r,mid+1,R,w);}
}seg;inline ll quick_pow(ll x,int y)
{ll ans = 1;while(y){if(y&1) ans = x * ans;x = x * x;y >>= 1;}return ans;
}inline ll get(int x,int z) { return f[x] + quick_pow(abs(sum[z] - sum[x] + z - x - 1 - l),p); }inline bool check(int x,int y) { return get(seg.find(1,1,n,x),x) > get(y,x) ; }inline void solve()
{seg.pre();read(n); read(l); read(p);rep(i,1,n){scanf("%s",s + 1);a[i] = strlen(s + 1);sum[i] = sum[i - 1] + a[i];fa[i] = i - 1;}rep(i,1,n){f[i] = get(seg.find(1,1,n,i),i);int l = i + 1 ,r = n,mid,ans = -1;while(l <= r){if(check(mid = l + r >> 1,i)) r = mid - 1,ans = mid;else l = mid + 1;}if(~ans) seg.modify(1,1,n,ans,n,i);}if(f[n] > inf) puts("Too hard to arrange");else printf("%lld\n",(long long)f[n]);puts("--------------------");
}int main()
{int t;read(t);while(t -- ) solve();return 0;
}

这篇关于1563: [NOI2009]诗人小G的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---