前言
来到产业园第一次写题 最近做的题目很杂 涉及很多个平台 vj loj cf 牛客 lg 然后等会一个个找吧 按照时间顺序写吧
一直拖着 没写题解 最近状态一般 想回家了
第一个题
这个题 我没写出来 因为我不会处理第二个平台的问题 谁能想到只需要记好第一个就行了呢
利用一个while循环记录 很好的trick
for(int i=1;i<=n;i++)
{
while(x[r]-x[i]<=k&&r<=n)r++;
f[i]=r-i;
}
maxn=max(maxn,f[i]+hsum[f[i]+i]);
//这种双指针不仅仅配合sum
//我不知道怎么处理两条 而且也没想到 使用后缀最大值去记录答案
//至于你说的这个while循环 我是想了的 可是我就是没想到怎么处理第二条
//哪知道第二条只需要记录后缀即可 反正一定不相交
//可惜可惜
第二个题
7.15我在看牛客的dp 顺手写的
第三个
听雨巨讲的 这个题
做了蛮久的 对于田忌来说 他只有两个选择 要么拿最好的马
要么拿最差的马 中间的马是没用的
对于
田鸡 2 3
齐王 1 3
并不是说最大打不赢就一定上早少的 不然上面那个就是平的 所以我们其实可以观察到
这个状态方程式只跟首尾有关
dp[l][r]=max(dp[l+1][r],dp[l][r-1]分别表示选l和r的情况
所以这题实际上需要对田鸡从大到小排序 对齐王从小到大排序 这样才满足我们的想法
我测试了齐王从小到大也行 他顺序没用影响 这个排序因人而异
然后就可以做出来了
点击查看代码
//#include <bits/stdc++.h>
//#define int long long
//#define endl '\n'
//#define debug cout<<endl<<"----------"<<endl;
//using namespace std;
//const int range = 4e3 + 10;
//int n;
//int a[range];
//int tian[range];
//int qi[range];
//int dp[range][range];
//int calc(int x,int y)
//{
// if(tian[x]>qi[y])return 200;
// else if(tian[x]==qi[y])return 0;
// else return -200;
//}
//void solve() {
// cin >> n;
// for (int i = 1; i <= n; i++)cin >> tian[i];
// for (int i = 1; i <= n; i++)cin >> qi[i];
// sort(tian + 1, tian + 1 + n);
// sort(qi + 1, qi + 1 + n);
// //92 83 71
// //85 87 74
// for (int len = 1; len <= n; len++) {
// for (int l = 1; l + len - 1 <= n; l++) {
// int r=l+len-1;
// dp[l][r]=max(dp[l+1][r]+calc(l,len),dp[l][r-1]+calc(r,len));
//// debug
//// cout<<dp[l][r]<<" "<<l<<" "<<r<<endl;
//// cout<<calc(l,len)<<" "<<calc(r,len)<<endl;
////牛魔 洛谷竟然能过
// }
// //r-l+1=n-k+1
// //k=n-len+1
// }
// cout<<dp[1][n];
//}
//signed main() {
// ios::sync_with_stdio();
// cin.tie(0);
// cout.tie(0);
// solve();
// return 0;
//
//
//}
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug cout<<endl<<"----------"<<endl;
using namespace std;
const int range = 4e3 + 10;
int n;
int a[range];
int tian[range];
int qi[range];
int dp[range][range];
int calc(int x,int y)
{
if(tian[x]>qi[y])return 200;
else if(tian[x]==qi[y])return 0;
else return -200;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> tian[i];
for (int i = 1; i <= n; i++)cin >> qi[i];
for(int i=1;i<=3100;i++)
{
for(int j=1;j<=3090;j++)dp[i][j]=-1e9;
}
sort(tian + 1, tian + 1 + n, greater<int>());
sort(qi + 1, qi + 1 + n);
for(int i=1;i<=n;i++)
{
dp[i][i]=calc(i,1);
}
// 10 3 3 2 2 1
// 10 9 9 8 7 6
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r=l+len-1;
// debug
// cout<<dp[l][r]<<endl;
dp[l][r]=max(dp[l][r],max(dp[l+1][r]+calc(l,len),dp[l][r-1]+calc(r,len)));
// cout<<dp[l][r]<<" "<<l<<" "<<r<<endl;
// cout<<calc(l,len)<<" "<<calc(r,len)<<endl;
// cout<<len<<" ";
}
//r-l+1=n-k+1
//k=n-len+1
}
//cout<<endl;
cout<<dp[1][n];
}
signed main() {
ios::sync_with_stdio();
cin.tie(0);
cout.tie(0);
solve();
return 0;
}