CF255--D--优先队列

这题的确是个好题~ 当时只觉得应该用贪心做...

后来人家给我证明了下不应该是用贪心局部最优解与全局最优解之间的关系不是严格成立的~

慢慢静心下来总是有解决的方法的=-=

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int size = 1000010;
 8 const LL inf = 1e18;
 9 LL a[1010] , b[1010];
10 LL row[size] , col[size];
11 priority_queue<LL>rowQu,colQu;
12 
13 int main()
14 {
15     cin.sync_with_stdio(false);
16     LL n , m , k , p , i , j , num , ans , temp;
17     while( cin >> n >> m >> k >> p )
18     {
19         for( i = 1 ; i<=n ; i++ )
20         {
21             for( j = 1 ; j<=m ; j++ )
22             {
23                 cin >> num;
24                 a[i] += num;
25                 b[j] += num;
26             }
27             rowQu.push(a[i]); 
28         }
29         for( j = 1 ; j<=m ; j++ )
30         {
31             colQu.push(b[j]);
32         }
33         ans = -inf;
34         for( i = 1 ; i<=k ; i++ )
35         {
36             temp = rowQu.top();
37             rowQu.pop();
38             row[i] = row[i-1] + temp;
39             rowQu.push(temp-m*p);
40             
41             temp =  colQu.top();
42             colQu.pop();
43             col[i] = col[i-1] + temp;
44             colQu.push(temp-n*p);
45         }
46         for( i = 0 ; i<=k ; i++ )
47         {
48             temp = row[i] + col[k-i];
49             temp -= (i)*(k-i)*p;
50             if( temp>ans )
51                 ans = temp;
52         }
53         cout << ans << endl;
54     }
55     return 0;    
56 }

View Code

这里因为数据很大用到64位那么 ans就要设置得足够小... 一开始我就用自己惯用的0x3f3f3f3f 会wa的~

以后做好每场cf　　一般感觉我以后cf要贴出来的都是后来看别人的解题报告才学会的~

//今天睡到下午2点半才醒好累..... 世界杯终于结束了

today:

　　这是一个流行离开的世界但是我们都不擅长告别~

　　你终于活得如同一般人类学行为规范去掉了表情隐藏了情绪不带一丝人气成了橡皮人~

just follow your heart