x的范围是[1, 10],可以直接枚举。
void solve(){
cin>>x1>>x2>>x3;
int res = inf;
for(int i = 1; i <= 10; i++){
res = min(res, abs(i - x1) + abs(i - x2) + abs(i - x3));
}
cout<<res<<"\n";
}
依照题目意思,只有满足上下左右都小于本身的数才能进行aij = aij - 1的操作,因此进行操作的数最小减小到四个方向中最大的数,那么如果满足要求(大于四个方向的数)就把这个位置的数替换为四个方向的最大数即可(不用担心四个方向的数会减小,因为如果中间的数满足要求,那么它的四个方向的数肯定不满足要求,也就不会减小)。不过得注意不要取到边界。
void solve(){
cin>>n>>m;
vvi a(n + 2, vi(m + 2));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin>>a[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] > a[i - 1][j] && a[i][j] > a[i][j - 1] && a[i][j] > a[i][j + 1] && a[i][j] > a[i + 1][j]){
int tem = 0;
if(i - 1 >= 1)tem = max(tem, a[i - 1][j]);
if(j - 1 >= 1)tem = max(tem, a[i][j - 1]);
if(j + 1 <= m)tem = max(tem, a[i][j + 1]);
if(i + 1 <= n)tem = max(tem, a[i + 1][j]);
a[i][j] = min(a[i][j], tem);
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout<<a[i][j]<<" ";
}
cout<<"\n";
}
}
由题可知,我们可以根据给的m个索引对原字符串的字符进行替换,并且题目要求原字符串s的字典序要尽可能小,那么只要我们尽可能给小的索引赋值小的字符即可。
void solve(){
map <int,int> ma1;
map <char,int> ma2;
cin>>n>>m>>s;
vi c(m);
for(int i = 0; i < m; i++){
cin>>c[i];
ma1[c[i]] = 1;
}
cin>>s1;
for(int i = 0; i < m; i++){
ma2[s1[i]] ++;
}
for(auto x : ma1){
for(auto y : ma2){
if(y.second > 0){
s[x.first - 1] = y.first;
ma2[y.first] --;
break;
}
}
}
cout<<s<<"\n";
}
题目意思:将n个个位数中的某两个连续的个位数结合成一个十位数,然后在n - 1个数中间添加+/*。
首先,观察n的范围[2, 20],很小,那么我们就可以考虑一下模拟 + 贪心
方法一:模拟 + 贪心
思路:先枚举两个数进行结合,然后寻找结合过后的n - 1个数中是否有0存在,如果有直接输出0(有0,当然直接*0就好了),如果没有0,就要考虑+和*在什么情况下会让答案更优。
一、如果遇到1,就应当用*,因为只有可以比+少1
二、如果遇到大于1的数,用*的结果 >= 用+的结果,那么我们干脆全部用+
void solve(){
cin>>n>>s;
int res = inf;
for(int i = 0; i < n - 1; i++){
vi a;
for(int j = 0; j < n; j++){
if(i == j){
a.push_back(10 * (s[j] - '0') + (s[j + 1] - '0'));
j ++;
} else {
a.push_back(s[j] - '0');
}
}
int sum = 0, ans = 0, flag = 0;
map <int,int> ma;
for(int j = 0; j < n - 1; j++){
if(a[j] == 1)flag = 1;
else flag = 0;
sum += a[j];
if(flag == 1)ans ++;
ma[a[j]] = 1;
}
if(ma.count(0)){
cout<<"0\n";
return;
}
if(ma.size() == 1)ans = max(ans - 1, 0ll);
res = min(res, sum - ans);
}
cout<<res<<"\n";
}
方法二:状态机 + 线性dp
题目要求某一个位置进行结合操作之后的最小值,那么我们可以用状态机来表示某一时刻是否完成结合操作
定义dp[个位数的个数][2(是否完成结合)]
vector <vector> dp(n, vector<int>(2));
状态转移方程
dp[i][0] = min(dp[i - 1][0] + (s[i] - '0'), dp[i - 1][0] + (s[i] - '0'));
dp[i][1] = min(min(dp[i - 1][1] + (s[i] - '0'), dp[i - 1][1] * (s[i] - '0')), min(dp[i - 2][0] + (10 * (s[i - 1] - '0') + (s[i] - '0')), dp[i - 2][0] * (10 * (s[i - 1] - '0') + (s[i] - '0'))));
void solve(){
cin>>n>>s;
vector <vector<int>> dp(n, vector<int>(2));
dp[0][0] = (s[0] - '0');
dp[1][0] = min(dp[0][0] + (s[1] - '0'), dp[0][0] * (s[1] - '0'));
dp[1][1] = (s[0] - '0') * 10 +(s[1] - '0');
for(int i = 2; i < n; i++){
int x1 = (s[i] - '0'), x2 = ((s[i - 1] - '0') * 10 + (s[i] - '0'));
dp[i][0] = min(dp[i - 1][0] + x1, dp[i - 1][0] * x1);
dp[i][1] = min(min(dp[i - 1][1] + x1, dp[i - 1][1] * x1),min(dp[i - 2][0] + x2, dp[i - 2][0] * x2));
}
cout<<dp[n - 1][1]<<"\n";
}
先放代码,思路明天补
void solve(){
map <int,vector<int>> ma;
cin>>n>>k;
for(int i = 0; i < n; i++){
int x;
cin>>x;
ma[x % k].push_back(x);
}
int sum = 0, ans = 0;
for(auto x : ma){
auto a = x.second;
sort(a.begin(), a.end());
if(a.size() % 2 == 0){
for(int i = 0; i < a.size(); i += 2){
sum += (a[i + 1] - a[i]) / k;
}
}else {
ans ++;
int tem = 0;
for(int i = 1; i < a.size(); i += 2){
tem += (a[i + 1] - a[i]) / k;
}
int res = tem;
for(int i = 0; i < a.size() - 1; i += 2){
tem -= (a[i + 2] - a[i + 1]) / k;
tem += (a[i + 1] - a[i]) / k;
res = min(res, tem);
}
sum += res;
}
}
if(ans > 1)sum = -1;
cout<<sum<<"\n";
}
标签:tem,min,int,cin,954,Codeforces,++,Div,dp
From: https://blog.csdn.net/hsjwhe/article/details/144542585