https://codeforces.com/contest/1842
C题很像leetcode上买股票那几题的套路，直接dp就行
\(z=max\{i-j+1+g[j-1] (a[i]=a[j]) \}\),g[j]表示以i结尾的最大值，很显然可以将跟j有关的项分离出来，然后对于每种ai维护最大值即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#include<queue>
#include<bitset>
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define eb(x) .emplace_back(x)
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
//const ll mo=1e9+7;
const ll inf=1ll<<60; // check
const int N=2e5+5; // check
ll n,f[N],g[N],a[N],ans,z;
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
ans=0;
scanf("%lld",&n);
fo(i,1,n) scanf("%lld",&a[i]);
fo(i,1,n) {
f[i]=-inf;
g[i]=0;
}
fo(i,1,n) {
z=i+f[a[i]]+1;
ans=max(ans,z);
g[i]=max(g[i-1], z);
f[a[i]]=max(f[a[i]], g[i-1]-i);
}
printf("%lld\n",ans);
}
return 0;
}
D题看到n，m就很像图论题。
手玩几个样例就能发现最大值是最短路，然后直接根据最短路的值分层就好。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#include<queue>
#include<bitset>
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define mm(a,b) (node){(a),(b)}
#define eb(x) .emplace_back(x)
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
//const ll mo=1e9+7;
const ll inf=1ll<<60; // check
const int N=105; // check;
ll n,m,f[N][N],x,y,z,k;
ll a[N];
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%lld %lld",&n,&m);
fo(i,1,n) fo(j,1,n) f[i][j]=inf;
fo(i,1,n) f[i][i]=0;
fo(i,1,m) {
scanf("%lld %lld %lld",&x,&y,&z);
f[x][y]=f[y][x]=z;
}
fo(k,1,n) {
fo(i,1,n) fo(j,1,n) {
f[i][j]=min(f[i][j], f[i][k]+f[k][j]);
}
}
if (f[1][n]==inf) {
puts("inf");
return 0;
}
fo(i,1,n) a[i]=f[1][i];
sort(a+1,a+n+1);
k=unique(a+1,a+n+1)-(a+1);
while (a[k]>f[1][n]) k--;
printf("%lld %lld\n",f[1][n],k-1);
fo(i,2,k) {
fo(j,1,n) {
printf("%d",f[1][j]<a[i]);
}
printf(" %lld\n",a[i]-a[i-1]);
}
return 0;
}