HDU3507 Print Article(斜率优化DP)
2018-06-17 20:29:58来源:未知 阅读 ()
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 16213 Accepted Submission(s):
4992
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost
M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.
#include<cstdio> #include<cstring> using namespace std; const int MAXN = 1e6 + 10, INF = 1e9 + 10; int N, M, a[MAXN], s[MAXN], f[MAXN], q[MAXN]; int X(int x) { return s[x]; } int Y(int x) { return f[x] + s[x] * s[x]; } int check(int x, int y, int i) { return (Y(y) - Y(x)) <= (X(y) - X(x)) * 2 * s[i]; } int check2(int xx1, int yy1, int xx2, int yy2) { return ((Y(yy1) - Y(xx1)) * (X(yy2) - X(xx2))) >= ((Y(yy2) - Y(xx2)) * (X(yy1) - X(xx1))); } /*int slope(int x, int y) { return (Y(y) - Y(x)) / (X(y) - X(x)); }*/ int main() { //freopen("a.in", "r", stdin); while(scanf("%d %d", &N, &M) != EOF) { memset(f, 0, sizeof(f)); for(int i = 1; i <= N; i++) scanf("%d", &a[i]), s[i] = s[i - 1] + a[i]; int h = 0, t = 0; for(int i = 1; i <= N; i++) { // if(h < t) printf("%lf %lf\n", slope(q[h], q[h + 1]), (double)2 * s[i]); while(h < t && check(q[h], q[h + 1], i)) h++; f[i] = (f[q[h]] + (s[i] - s[q[h]]) * (s[i] - s[q[h]]) + M); while(h < t && check2(q[t - 1], q[t], q[t], i)) t--; q[++t] = i; } printf("%d\n", f[N]); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:OJ:析构函数实现多态
下一篇:多项式整理
- 小细节--关于printf的输出问题 2019-05-22
- 写高并发程序时慎用strncpy和sprintf 2019-01-05
- C++ 学习笔记(一) cout 与printf 的不同之处 2018-08-26
- printf函数 2018-06-18
- 关于 printf() 函数的三张表格 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash