成都市那里有网站建设制作公司,wordpress midway,江苏做网站怎么收费多少,医疗产品设计公司[USACO19JAN,Platinum] Redistricting
这道题A了才知道。。并不难a#xff01; orz
题目
内存限制#xff1a;128 MiB 时间限制#xff1a;1000 ms 题目描述 奶牛们的最大城市Bovinopolis正在重新划分势力范围—生活在那里的主要是两个品种的奶牛#xff08;Holsteins和…[USACO19JAN,Platinum] Redistricting
这道题A了才知道。。并不难a orz
题目
内存限制128 MiB 时间限制1000 ms 题目描述 奶牛们的最大城市Bovinopolis正在重新划分势力范围—生活在那里的主要是两个品种的奶牛Holsteins和Guernseys他们之间始终都有争执因为两种奶牛都希望自己能在Bovinopolis的政府中保持足够的影响力。
Bovinopolis的大都市区域由N1≤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牛控制的牧场。
输出格式 输出Guernseys牛占优或均势的最小分区数量。
样例 样例输入 7 2 HGHGGHG 样例输出 3
题解
首先一个长度为k的区间可以划分为1和k-12和k-2…k很多种选择 而在这中间每一种选择都会影响答案 而且与前面一次选择后k具体在哪个到哪个区间有关系
那么这道题就很容易想到DP了而且长得跟台阶问题很像
首先我们可以定义一个pre数组表示1~i区间中H比G多的个数 如果小于等于0的话就意味着G占优势答案1大于0则H占优势答案不变
我们先来处理最容易的DPdp[i]表示处理完i后的最小答案很容易就写出 dp[i] min ( dp[i], dp[i-j] ( pre[i] - pre[i - j] ) ≤ 0 ? 1 : 0 ) 1≤i≤n1≤j≤k 注意理解pre[i]-pre[i-j]实际上算的是[i-j1,i] 但是这样的dp是Onk肯定超时 我们得搞点事做个数据优化啥的 首先我们每个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不要太想我我怎么开始满嘴跑火车了
