知识点
1.Floyd算法的核心代码
//floyd算法计算到达两点的最小代价
for(int k=0;k<=n;k++)//n是节点数
{
for(int i=0;i<n;i++)//每加一个节点都要枚举图看看有没有可以被更新的
{
for(int j=0;j<n;j++) if(dp[i][j]>dp[i][k]+dp[k][j]) dp[i][j]=dp[i][k]+dp[k][j];
}
}
题解
D - Wall
1.使用floyd算法计算一下每个点到每个点到最小花费即可，然后输入查询相加即可
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int h,w; cin>>h>>w;
int dp[10][10];
for(int i=0;i<=9;i++)
{
for(int j=0;j<=9;j++) cin>>dp[i][j];
}
//floyd算法计算到达两点的最小代价
for(int k=0;k<=9;k++)
{
for(int i=0;i<=9;i++)
{
for(int j=0;j<=9;j++) if(dp[i][j]>dp[i][k]+dp[k][j]) dp[i][j]=dp[i][k]+dp[k][j];
}
}
int ans=0;
//输入查询相加即可
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
int x;
cin>>x;
if(x>=0) ans+=dp[x][1];
}
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
C - Minimization
1.这题我们思维定式会去找最小值的位置，其实跟最小值的位置没关系，因为一定会遍历到这个最小值，所以只要计算到最右边界的次数即可
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
}
int d=0,res=0;
while(d<n)
{
if(d==0) d+=m;
else d+=m-1;
res++;
}
cout<<res;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
Linear Approximation
1.令ci=ai-i;则题目就转化为求abs（ci-b）的和，那么只有当b为差值的中位数，对总和的贡献最小
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int n;
cin>>n;
vector<int>ve(n+1);
for(int i=1;i<=n;i++) {
cin>>ve[i];
ve[i]=ve[i]-i;
}
sort(ve.begin()+1,ve.end());
int temp=ve[n/2+1];
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=abs(ve[i]-temp);
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
C. Brutality
1.按题意来模拟，就是找几个连续字母代表的数字的最大和，但不能超过k次，也就是几个连续字母这段区间的前k个值（从大到小）的和，不足k个则全加进去
2.一段一段区间来处理，会使代码更加简洁快速
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
int n,m;
cin>>n>>m;
vector<int>ve(n);
for(int i=0;i<n;i++)
{
cin>>ve[i];
}
string s; cin>>s;
int ans=0;
for(int i=0;i<n;i++)
{
//遍历到几个连续相同的就进行一次处理
int j=i;
vector<int>fi;
while(j<n&&s[i]==s[j])
{
fi.push_back(ve[j]);
j++;
}
sort(fi.rbegin(),fi.rend());//从大到小排序
//accumulate函数中的这个min最关键，这样可以避免你还要重新去开几个查询的数组来找值的和
ans+=accumulate(fi.begin(),fi.begin()+min(m,(int)fi.size()),0);
i=j-1;
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
D - Equal Cut
1.我们把题目想象成，我们在一组已经排列好的数里面，选择3个位置放挡板
2.首先，我们肯定要枚举第二块挡板，先把这些数分为左右两个区间，然后在左右区间里面，在分别枚举一块合适的挡板
3.那么什么情况下最合适呢，当左右区间里的两个区间的绝对值差值最小是最合适的，因为题目要我们求最大和区间-最小和区间的值，也就是要让最小区间和尽量大，最大区间和尽量小，这样差值才会更小，所以当区间绝对值差值最小的时候，就可以满足了
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int sum[200005];
int js(int l,int r)//求区间的和
{
return sum[r]-sum[l-1];
}
void solve()
{
int n; cin>>n;
vector<int>ve(n+1);for(int i=1;i<=n;i++) cin>>ve[i];
for(int i=1;i<=n;i++) sum[i]=ve[i]+sum[i-1];
//枚举第二刀把其分为L R区间
int l=1,r=3;
int ans=1e9;
for(int i=2;i<=n-2;i++)//总共有n个元素第二刀最多切到n-2
{
while(l+1<i&&abs(js(1,l)-js(l+1,i))>=abs(js(1,l+1)-js(l+2,i))) l++;
//相当于你在L这个区间 找位置切，直到找到L里左右区间差值最小
//差值最小能够保证我们前面有一个使减数尽量大的区间
while(r+1<n&&abs(js(i+1,r)-js(r+1,n))>=abs(js(i+1,r+1)-js(r+2,n))) r++;
//在R区间是同理的
set<int>se;
//set自动从小到大排序
se.insert(js(1,l));
se.insert(js(l+1,i));
se.insert(js(i+1,r));
se.insert(js(r+1,n));
ans=min(ans,abs(*se.begin()-*prev(se.end())));//prev用来获取最后一个值的地址
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}