【HDOJ】4261 Estimation

摘要:
一个很好的问题。基本思想是dp。关键是如何在区间内找到Sigma|A线段树是TLE,优先级队列可以通过。

挺不错的一道题,基本思路是dp。关键点是如何求区间内的Sigma|A_i-B_i|。
线段树做TLE了,优先队列可以过。

  1 /* 4261 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 const int INF = 1e9;
 44 const int maxn = 2005;
 45 const int maxm = 30;
 46 int n, m;
 47 int a[maxn];
 48 int dp[maxm][maxn];
 49 int dif[maxn][maxn];
 50 
 51 void solve() {
 52     int tmp;
 53     
 54     rep(i, 1, n+1) {
 55         priority_queue<int> q;
 56         priority_queue<int, vi, greater<int> > Q;
 57         
 58         int ls, rs;
 59         int ln, rn;
 60         int x, xx;
 61         int l = 0;
 62         
 63         ln = rn = 0;
 64         ls = rs = 0;
 65         rep(j, i, n+1) {
 66             ++l;
 67             x = a[j];
 68             if (l & 1) {
 69                 ++ln;
 70                 if (rn && Q.top()<x) {
 71                     xx = Q.top();
 72                     Q.pop();
 73                     q.push(xx);
 74                     ls += xx;
 75                     Q.push(x);
 76                     rs += x - xx;
 77                 } else {
 78                     q.push(x);
 79                     ls += x;
 80                 }
 81                 
 82                 x = q.top();
 83                 tmp = rs - ls + x;
 84                 dif[i][j] = tmp;
 85             } else {
 86                 ++rn;
 87                 if (q.top() > x) {
 88                     xx = q.top();
 89                     q.pop();
 90                     Q.push(xx);
 91                     rs += xx;
 92                     q.push(x);
 93                     ls += x - xx;
 94                 } else {
 95                     Q.push(x);
 96                     rs += x;
 97                 }
 98                 
 99                 x = q.top();
100                 tmp = rs - ls;
101                 dif[i][j] = tmp;
102             }
103         }
104     }
105     
106     rep(j, 1, n+1) {
107         dp[1][j] = dif[1][j];
108     }
109     
110     rep(i, 2, m+1) {
111         rep(j, i, n+1) {
112             dp[i][j] = INF;
113             rep(k, i-1, j) {
114                 dp[i][j] = min(dp[i][j], dp[i-1][k]+dif[k+1][j]);
115             }
116         }
117     }
118     
119     printf("%d
", dp[m][n]);
120 }
121 
122 int main() {
123     ios::sync_with_stdio(false);
124     #ifndef ONLINE_JUDGE
125         freopen("data.in", "r", stdin);
126         freopen("data.out", "w", stdout);
127     #endif
128     
129     while (scanf("%d %d", &n, &m)!=EOF && (n||m)) {
130         rep(i, 1, n+1) {
131             scanf("%d", &a[i]);
132         }
133         solve();
134     }
135     
136     #ifndef ONLINE_JUDGE
137         printf("time = %d.
", (int)clock());
138     #endif
139     
140     return 0;
141 }

数据生成器。

 1 from random import randint, shuffle
 2 import shutil
 3 import string
 4 
 5 
 6 def GenDataIn():
 7     with open("data.in", "w") as fout:
 8         t = 22
 9         bound = 10**4
10         for tt in xrange(t):
11             n = randint(1800, 2000)
12             k = randint(1, 25)
13             fout.write("%d %d
" % (n, k))
14             dataList = []
15             for i in xrange(n):
16                 x = randint(-bound, bound)
17                 dataList.append(x)
18             fout.write(" ".join(map(str, dataList)) + "
")
19         fout.write("0 0
")        
20         
21                 
22 def MovDataIn():
23     desFileName = "F:eclipse_prjworkspacehdojdata.in"
24     shutil.copyfile("data.in", desFileName)
25 
26     
27 if __name__ == "__main__":
28     GenDataIn()
29     MovDataIn()

免责声明:文章转载自《【HDOJ】4261 Estimation》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇【HDOJ】2388 Playground Hideout[转]SQLSERVER 18056 错误下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

Linux环境(五)--主机信息与日志

主机信息正如我们可以确定用户信息一样,程序也可以确定其运行的计算机的信息。uname命令提供了这些信息。uname同时也作为一个系统调用来在一个C程序中提供同样的信息,我们可以使用man 2 uname来查看详细的信息。许 多情况都需要主机信息。我们也许希望依据在网络中一个程序所运行的机器的名字来自定义其行为,也就是说,是一个学生的机器还是一个管理员的机器。...

Linux下的静态库和动态库 yg2362 C++博客

Linux下的静态库和动态库 - yg2362 - C++博客 Linux下的静态库和动态库 1.制作自己的动态库和静态库 linux下动态库以.so结尾,静态库以.a结尾,它们都以lib开头,比如一个库名为net,那么它的全名应该是libnet.so或者libnet.a。 我们有两个文件,hello.c和test.c,下面是两个文件的内容 //hell...

关于时间管理

最近晚上睡得比较迟,但是也静不下心来看书,如何能调整一下呢 1)每天上下午吃个苹果和梨还有开水来,一来一段时间起来走动一下,活动一下劲骨,二来长时间坐着人就容易累了 2)7点前吃饭,我分析之所以晚上1-2点还睡不着,也可能和吃得比较迟有关系,能量还在释放中。。。,不是有说睡前不要吃东西 3)保持一天一个持续的体力工作战到10点左右,要保持一天工作12小时,正...

Android TabWidget

首先先看一个小例子,接着讲解原理 TabTest.java viewplaincopytoclipboardprint? packageorg.hualang.tab; importandroid.app.Activity; importandroid.app.TabActivity; importandroid.graphi...

Example code for using the Selenium 2 Python bindings. — Gist

Example code for using the Selenium 2 Python bindings. — Gist # To install the Python client library: # pip install -U selenium # Import the Selenium 2 namespace (aka "webdriver")...

ARM指令集及混合编程

一、ARM指令集 1、跳转指令:B、BL(带返回)、BLX、BX(带状态) 2、数据传送:MOV(通用寄存区)、MVN(按位取反)、CMP(比较结果存在CPSR)、TST(按位置位)、ADD、SUB、AND、ORR、BIC、MUL、 3、访问状态寄存器:MSR、MRS 二、汇编指令集 1、LDR、STR(B) 2、STR、 3、LDM、STM (批处理) 4...