[USACO19JAN,Platinum] Redistricting

這道題A了才知道。。并不難a！ orz

題目

內存限制：128 MiB
時間限制：1000 ms
題目描述
奶牛們的最大城市Bovinopolis正在重新劃分勢力范圍—生活在那里的主要是兩個品種的奶牛（Holsteins和Guernseys），他們之間始終都有爭執，因為兩種奶牛都希望自己能在Bovinopolis的政府中保持足夠的影響力。

Bovinopolis的大都市區域由N（1≤N≤3*1e5）個牧場組成，每個牧場包含一頭奶牛，她可以是Holsteins，也可以是Guernseys。

Bovinopolis政府希望將大都市區劃分為若干個相鄰的區域，每個區域最多包含K個牧場（1≤K≤N），每個牧場都恰好只包含在一個區域內。由于目前Bovinopolis政府由Holsteins牛控制，因此，他們希望找到一種重新劃分的方法，使得Guernseys牛占多數或兩種牛相當的區域盡可能的少（如果Guernseys的數量和Holsteins的數量相同，則認為是兩種牛相當）。

有一個關心政治的Guernseys牛的聯盟想知道政府的計劃會對她們造成多少的傷害，希望你幫助她們計算出Guernseys牛占優或實力相當的區域最小可能的數量。

輸入格式
第一行輸入2個數字N和K，表示牧場的數量和每個區域最多的牧場數。

第二行輸入N個只包含H和G的字符串，表示第i個牧場由Holsteins牛或Guernseys?？刂频哪翀觥?/p>

輸出格式
輸出Guernseys牛占優或均勢的最小分區數量。

樣例
樣例輸入
7 2
HGHGGHG
樣例輸出
3

題解

首先一個長度為k的區間，可以劃分為1和k-1，2和k-2…k，很多種選擇，
而在這中間每一種選擇都會影響答案，
而且與前面一次選擇后k具體在哪個到哪個區間有關系

那么這道題就很容易想到DP了，而且長得跟臺階問題很像！

首先我們可以定義一個pre數組，表示1~i區間中，H比G多的個數
如果小于等于0的話，就意味著G占優勢，答案+1，大于0則H占優勢，答案不變

我們先來處理最容易的DP，dp[i]表示處理完i后的最小答案，很容易就寫出：
dp[i] = min ( dp[i], dp[i-j] + ( pre[i] - pre[i - j] ) ≤ 0 ? 1 : 0 )
1≤i≤n，1≤j≤k，
注意理解pre[i]-pre[i-j]實際上算的是[i-j+1,i]
但是這樣的dp是O（nk）肯定超時！！
我們得搞點事，做個數據優化啥的！

首先我們每個i只會在外層循環1次，找到1~i-1之前加上i后最小的答案
所以就是求dp[i]=min{dp[i-j] + ( pre[i] - pre[i - j] ) ≤ 0 ? 1 : 0}

這就可以想到堆優化，用優先隊列維護，每一次就取隊列的top
那么意思是我要維護這個隊列一定和i是合法的，
而且對答案的值貢獻是從小到大的

來思考一下dp[i-j] + ( pre[i] - pre[i - j] ) ≤ 0 ? 1 : 0
發現 ( pre[i] - pre[i - j] ) ≤ 0 對于答案的影響只有1/0
真正影響的是dp[i-j]，所以這個隊列我們就可以先維護dp[i-j]從小到大
當dp[i-j]相同時，再維護( pre[i] - pre[i - j] ) ≤ 0從小到大

那么我們就把dp值和下標i丟到隊列里，讓隊列幫我們排序就好啦！

代碼實現

#include <cstdio> #include <queue> using namespace std; #define MAXN 300005 int n, k; char s[MAXN]; int dp[MAXN]; int pre[MAXN]; struct node {int val, id;bool operator < ( const node &t ) const {if ( val == t.val ) return pre[id] > pre[t.id];return val > t.val;} }; priority_queue < node > q; int main() {scanf ( "%d %d %s", &n, &k, s );for ( int i = 1;i <= n;i ++ ){if ( s[i - 1] == 'H' )pre[i] = pre[i - 1] + 1;elsepre[i] = pre[i - 1] - 1;dp[i] = 0x7f7f7f7f;}q.push ( ( node ) { 0, 0 } );for ( int i = 1;i <= n;i ++ ) {while ( ! q.empty() && q.top().id < i - k ) q.pop();dp[i] = ( pre[i] - pre[q.top().id] <= 0 ) ? q.top().val + 1 : q.top().val; q.push ( ( node ) { dp[i], i } );}printf ( "%d", dp[n] ); }

日更爆肝！真愛生命！遠離熬夜，保健品你值得擁有

誘人問題都可以留言，我們有緣再見！bye不要太想我我怎么開始滿嘴跑火車了？

總結

以上是生活随笔為你收集整理的[USACO19JAN，Platinum] Redistricting的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。