题目的意思是有个打印机很老了,现在要打印单词,每个单词打印都有耗费价值,每次打印几个单词都符合题目给出的式子:
问,最少的耗费价值。第一次接触概率dp,介绍几篇题解吧,结合起来看更好理解。
http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html(针对这个题讲的很容易懂,但是中间有些错误,还请不要纠结,下面评论区有指正。)
http://www.cnblogs.com/kuangbin/archive/2012/08/26/2657650.html(结合上一片博客食用更佳,看完上面的如果纠结错误,看这篇可以解惑)
http://blog.csdn.net/lxc779760807/article/details/51366552(斜率dp优化小结,写的不错)
代码:
Status | Accepted |
---|---|
Time | 249ms |
Memory | 7524kB |
Length | 1255 |
Lang | C++ |
#include <iostream> #include <cstdio> using namespace std; const int maxn=500005; int n, m; int dp[maxn], sum[maxn], que[maxn]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int getDp(int i, int j){ return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m; } int getUp(int j, int k){ return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k]; } int getDown(int j, int k){ return 2*(sum[j]-sum[k]); } int main() { while(~scanf("%d%d", &n, &m)){ sum[0]=dp[0]=0; for(int i=1;i<=n;i++){ sum[i]=read(); sum[i]+=sum[i-1]; } int head=0, tail=0; que[tail++]=0; for(int i=1;i<=n;i++){ while(head+1<tail && getUp(que[head+1], que[head])<=sum[i]*getDown(que[head+1], que[head])) head++; //找到最优解 dp[i]=getDp(i, que[head]); while(head+1<tail && getUp(i, que[tail-1])*getDown(que[tail-1], que[tail-2])<=getDown(i, que[tail-1])*getUp(que[tail-1], que[tail-2])) tail--; //删除斜率变小的点 que[tail++]=i; //当前点放入队列 } printf("%d\n", dp[n]); } return 0; }