2020 ICPC沈阳站-D,HD. Journey to Un'Goro (思维)H. The Boomsday Project (DP)

57 阅读 0 评论 38 点赞

我是靠谱客的博主大方蜜粉，最近开发中收集的这篇文章主要介绍2020 ICPC沈阳站-D,HD. Journey to Un'Goro (思维)H. The Boomsday Project (DP)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

~~icpc好难啊，希望有生之年能拿牌ort.....~~

D. Journey to Un'Goro (思维)

链接：https://codeforces.com/gym/103202/problem/D

Recently, you've taken a trip to Un'Goro.

A small road in Un'Goro has attracted your eyes. The road consists of n steps, each colored either red or blue.

When you go from the iith step to the jth, you count the number of red steps you've stepped. You will be satisfied if the number is odd.

"What is the maximum number of pairs (i,j) (1≤i≤j≤n), such that I'll be satisfied if I walk from the ith step to the jth?" you wonder. Also, how to construct all colorings such that the number of pairs is maximized?

Input

The only line contains an integer n (1≤n≤1e5), indicating the number of steps of the road.

Output

Output an integer in the first line, denoting the maximum number of pairs that make you satisfied.

Each of the following several lines contains a string with length n that represents a coloring scheme, in lexicographically ascending order. The ith character is the color of the ith step, where r is for red and b for blue.

If there are more than 100 different colorings, just find the lexicographically smallest 100 colorings.

Note that in lexicographical order, b is ordered before r.

Examples

input
1
output
1
r
input
2
output
2
br
rb
rr
input
3
output
4
brb
rbr
rrr

题意：定义一个令人满意的字符串区间为区间内'r'字符的个数为奇数。给定一个字符串长度，求只用'b'和'r'字符构建字符串，最多能得到多少个令人满意的区间，并求出满足有最多满意的区间个数的所有字符串，最多输出100个。

用一个数组p[i]存储长度为i的字符串前缀中r的个数，则区间[l, r]中'r'的个数等于p[r] - p[l-1]。所以可知如果区间[l, r]内的'r'个数是奇数，那么p[r]和p[l-1]的奇偶性必然不同，其中一个数必然是奇数，另一个必然是偶数，因为如果两个同时是奇数或偶数，那么两个相减必然是偶数。

所以这一题可以转化成求p数组中最多有多少个奇数和偶数的对数，显然可知，当奇数个数[(n+1)/2]，偶数个数[(n+1)/2]时对数最多（+1是因为包括p[0]）。所以，满足条件的最多个数为 [n/2]*[n/2]。

然后题目要求输出满足最大个数的字符串，由于字符串要求最多只输出100个，所以可以直接用暴力搜索实现。可知只有i的位置上放'r'时，才能改变pi的奇偶性，所以如果pi-1==pi，那么相当于在i位置放'b'，反之则是放'r'。

代码如下：

#include<iostream>
using namespace std;
const int N = 1e+5;
int p[N]; //p[i]表示长度为i的字符串前缀中r的个数
long long n;
int cnt = 0; //存输出的字符串个数
string s; //存答案字符串
void dfs(int idex, int odd, int even, bool fg) //idex表示当前位置，odd表示奇数个数，even表示偶数个数，fg表示p[idex-1]是奇数还是偶数
{
if(odd>(n+2)/2 || even>(n+2)/2) return ; //奇数个数和偶数个数不满足得出答案的要求，退出
if(idex==n)
{
cout << s << endl; //输出答案字符串
if(++ cnt>=100) exit(0); //超过100了，直接退出
return ;
}
s += 'b';
dfs(idex+1, odd+fg, even+(fg^1), fg); //当前位置放b的情况
s.pop_back();
s += 'r';
dfs(idex+1, odd+(fg^1), even+fg, fg^1); //当前位置放r的情况
s.pop_back();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
cout << (n+1)/2*((n+2)/2) << endl;//0 1 2 3 4 5 6
dfs(0, 0, 1, 0);
return 0;
}

H. The Boomsday Project (DP)

链接：https://codeforces.com/gym/103202/problem/H

Aloha is a poor guy who likes riding a bike. But he is too poor to afford a bicycle.

Recently, the Boom's bike-sharing service entered his school. It only costs r yuan for every single rent of a bicycle. From then on, Aloha could rent a bike and enjoy the speed and passion of riding.

The Boom's company has launched a promotion program named the Boomsday Project. In this program, users can buy discount cards with several free rents and a valid period. For example, after purchasing a discount card with k free rents and d days of valid time, one doesn't need to pay extra fees for the following k rents in the next d days. Note that, no matter when the card is bought on day t, it will always expire at the end of day t+d−1. Also, any new discount card overrides the previous one even if it is still valid, i.e., the remaining free rents of the previous discount card are voided immediately when the new discount card is purchased.

There are n different types of discount cards in the Boomsday Project. A card of ith type with ki free rents and a valid period of di days costs ci yuan. One can buy any type of discount card unlimited times.

Given the rental records, Aloha wants to know the minimum money he has to pay, provided that he takes the best strategy.

Input

The first line of input contains three integers n,m,r(1≤n≤500,1≤m≤105,1≤r≤109), denoting the number of discount card types, the number of rental records, and the price of a single rent.

Then follow n lines, specifying the n types of discount cards. The ith line contains three integers di,ki,ci (1≤di,ki,ci≤1e9), denoting the valid period, the number of free rents, and the price of a discount card of type i.

The last m lines describe Aloha's rental records. The ith of them contains two integers pi,qi (0≤pi≤1e9,0≤qi≤3×1e5, $sum_{i=1}^m q_{i}leqslant 3times 10^{5}$ ), representing that Aloha would rent bikes qi times on Day pi. It is guaranteed that p1,p2,⋯,pm are distinct.

Output

Print one integer in a line, denoting the minimum money Aloha has to pay if he adopts the best strategy.

Examples

input
2 1 10
1 3 12
1 2 9
1 10
output
42
input
2 4 10
1 3 12
1 2 9
1 3
2 3
3 3
4 1
output
45

题意：某个租车店有两种租车方法，第一种直接租车，花费r元。第二种是有n种类型的卡，买完i种类型的卡后在接下来的有效期di天(now+di-1)，可以免费租车ki次，买卡花费ci元。某人决定在某些天qi租车，租车pi次，求他租完所有次数后花费的最小金额。

该题用dp。dp[i]表示租车到第i次所需的最小花费。租赁的方式有两种，一种是单独租，每租一辆花费r。另一种方式是花费c购买张有效期为d天可以免费租车k次的卡。对于第一种租赁方式显然可以得到dp[i] = dp[i-1]+r的方程。

对于第二种则可以分为两种情况，第一种情况则是d天内k次免费租车都可以使用完。
另一种就是只能使用一部分(即当天不再需要租车了，剩下的次数只能在下一次租赁时使用，但下一次在当前卡的有效期范围外或者没有下一次的情况)。

所以可得：设当前为第i次租赁,使用第j张卡，那么如果d[j]内k[j]可以全部得到使用则：

dp[i+k[j]-1] = min(dp[i+k[j]-1, dp[i-1]+c[j]).

反之则设当前这张卡可以最多可以租到第pos次的车, 则:

dp[pos] = min(dp[pos], dp[i-1]+c[j]).

对于pos的求法，只需把每次租车记录先按天从小到大排序，再记录每次的租车所在的天数，然后通过二分找到最后一个小于等于 第i次租车所在天数+d[j]-1 的那个位子即可。

具体实现看代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5+5;
int sum=0, dp[N], d[N], c[N], k[N]; //sum记录租车总次数，d[i], c[i], k[i]表示第i张卡的有效期,价格和免费租车次数
int to[N]; //to[i]表示第i次租车所在的天数
PII q[N]; //用来存租车记录
int find(int tar) //二分找到最后一个小于等于to[i]+d[j]-1的所在
{
int l = 1, r = sum;
while(l<r)
{
int mid = l + r + 1 >> 1;
if(to[mid]<=tar) l = mid;
else r = mid - 1;
}
return l;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, r;
cin >> n >> m >> r;
for(int i=0; i<n; i++) cin >> d[i] >> k[i] >> c[i];
for(int i=0; i<m; i++) cin >> q[i].first >> q[i].second;
sort(q, q+m);
for(int i=0; i<m; i++)
{
sum += q[i].second; //求总的租车次数
for(int j=sum-q[i].second+1; j<=sum; j ++) //求这些租车次数都在第几天
to[j] = q[i].first;
}
memset(dp, 0x3f, sizeof(dp)); //初始化dp数组
dp[0] = 0;
for(int i=1; i<=sum; i++)
{
dp[i] = min(dp[i], dp[i-1]+r); //单独租车的情况
for(int j=0; j<n; j++)
{
if(i+k[j]-1<=sum && to[i+k[j]-1]<=to[i]+d[j]-1) //可以把k次全部租完的情况
dp[i+k[j]-1] = min(dp[i+k[j]-1], dp[i-1]+c[j]);
else //不能全部租完的情况
{
int pos = find(to[i]+d[j]-1); //查找最后一个小于等于to[i]+d[j]-1的所在
dp[pos] = min(dp[pos], dp[i-1]+c[j]);
}
}
}
cout << dp[sum] << endl;
return 0;
}