这场签到很快那会rank1400吧，但到c就写不动了，最后排名也是3000
左右，可见很多人其实都不会写dp。快速签到也很重要啊！！
A. Two Friends
Problem - A - Codeforces
题目大意：
M有n个朋友，编号1-n，如果朋友i来则必须pi需要收到邀请，求来2个朋友至少需要发出多少邀请函。
思路：
这题我照着样例摸了一下，一眼感觉就是如果pi=j并且pj=i就只需要邀请两个人，否则至少邀请三个人。至于为什么邀请三个人一定能满足条件当时没有细想，猜了结论交上去就a了。
那么现在来看一下，1 2 3 4
3 4 2 1这种就是至少要邀请三个人的情况了，如果我想要1来就得邀请3，如果3来就得邀请2，所有只要邀请123就一定至少有2个人来。很显而易见了hhhh。
#include<bits/stdc++.h>
using ll=long long;
const int N=5000+10;
const int mod=998244353;
int a[N];
std::map<char,int> mp;
void solve()
{
int n;
std::cin>>n;
for(int i=1;i<=n;i++)
{
std::cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i]==j&&a[j]==i)
{
std::cout<<2<<'\n';
return;
}
}
}
std::cout<<3<<'\n';
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t=1;
std::cin>>t;
while(t--)
{
solve();
}
return 0;
}B. Shifts and Sorting
Problem - B - Codeforces
题目大意：
给定一个只含01的字符串，要求把它变成非递减的。每次可以做变换，如把1000->0100，每次操作其中一个子串把最后一位放到第一位，如把10子串变成01花费2。
思路：
这题我当时照着样例推了一遍，
5
10 最后结果一定是01，要求次数最少，01，花费2
0000 所有位相同花费0
11000 最后结果一定是00011，要求次数最少，第一个1一定要移到后面，所以每有个0都得交换。11000->01100->00110->00011 花费3+3+3=9
101011 最后结果一定是001111，101011->011011->001111 2+3=5
01101001 最后结果一定是00001111，01101001->00111001->00011101->00001111 3+4+4=11其实推完样例结果就很容易出来了（也就是说比赛的时候一定要静下心来认真推样例）。只需要对第一个1操作，把所有0都移到他的前面去，这个串就是非递减的了。每一次操作完之后都会有一个0跑到前边去，所以花费可以减少1。
#include<bits/stdc++.h>
using ll=long long;
const int N=5000+10;
const int mod=998244353;
int a[N];
std::map<char,int> mp;
void solve()
{
std::string s;
std::cin>>s;
ll ans=0;
int ind=-1;
for(int i=0;i<=s.length();i++)
{
if(s[i]=='1')
{
ind=i;
break;
}
}
ll cnt=0;
if(ind==-1)
{
std::cout<<0<<'\n';
return ;
}
for(int i=ind+1;i<s.length();i++)
{
if(s[i]=='0')
{
ans+=i-ind+1-cnt;
cnt++;
}
}
std::cout<<ans<<'\n';
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t=1;
std::cin>>t;
while(t--)
{
solve();
}
return 0;
}C. Minimizing the Sum
Problem - C - Codeforces
题目大意：
给定一个序列，每次操作可以把其中一个数的左边/右边变得跟他一样，例如：
𝑎=[3,1,2], you can get one of the arrays [3,3,2], [3,2,2] and [1,1,2]。最多操作k次，输出这个序列的最小总和。
思路：
这题我写的时候一眼贪心啊，敲了个优先队列存储pair，敲完突然想到好几个hack样例，贪心包过不了的啊。然后感觉这个很像dp了，但是本人dp写得极少，确实写不出来。（菜就多练.jpg）。
代码思路很清晰，看代码吧。
#include<bits/stdc++.h>
using ll=long long;
#define int ll
const int N=1e6+10;
const int mod=998244353;
using PII=std::pair<int,int>;
int a[N];
int dp[N][15];//对前i个数操作j次
void solve()
{
int n,k;
std::cin>>n>>k;
for(int i=1;i<=n;i++)
{
std::cin>>a[i];
}
a[0]=1e9,a[n+1]=1e9;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
dp[i][j]=dp[i-1][j]+a[i];
}
for(int j=0;j<=k;j++)//之前已经操作了多少次
{
for(int p=0;p+j<=k&&p<=i;p++)//当前要操作多少次
{
dp[i][j+p]=std::min(dp[i][j+p],dp[i-p][j]+p*std::min(a[i+1],a[i-p]));
}
}
}
std::cout<<dp[n][k]<<'\n';
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
//freopen("a.txt","r",stdin);
//freopen("b.txt","w",stdout);
int t=1;
std::cin>>t;
while(t--)
{
solve();
}
return 0;
}D. Shop Game
Problem - D - Codeforces
题目大意：
商店里有n个商品，对alic的价格是ai，bob的价格是bi。
alice每次能从中买商品：
如果个数小于k，bob能免费全拿走。
否则，bob会从alice手中免费拿走k个，其余的付bi购买。
如果alice让自己的利润最大，bob让alice的利润最小，输出alice最后的利润。
思路：
偷个别人的题解，我悟了。
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<numeric>
#include<algorithm>
using namespace std;
using LL = long long;
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--)
{
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) cin >> b[i];
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y)
{
if (b[x] != b[y]) return b[x] > b[y];
return a[x] < a[y];
});
LL s1 = 0, s2 = 0, ans = 0;
set<pair<int, int> > s;
for(int i = 0; i < k; i++)
{
s.insert({a[id[i]], id[i]});//b免费拿走的
s1 += a[id[i]];
}
for(int i = k; i < n; i++)
{
if (b[id[i]] > a[id[i]])
{
s2 += b[id[i]] - a[id[i]];//利润
}
}
for(int i = k; i < n; i++)
{
ans = max(ans, s2 - s1);//存最大利润
if (b[id[i]] > a[id[i]])
{
s2 -= b[id[i]] - a[id[i]];
}
s.insert({a[id[i]], id[i]});
s1 += a[id[i]];
s1 -= prev(s.end())->first;
s.erase(prev(s.end()));
}
cout << ans << '\n';
}
}
