复习

AcWing 1242. 修改数组（周一）

前言

我先复习一遍昨天写的题，然后再开始写今天的题。

#include<bits/stdc++.h>
using namespace std;const int N=1e6+1e5+10;int p[N];int find(int x){if(x!=p[x]){p[x]=find(p[x]);}return p[x];
}int main(){int n;cin>>n;for(int i=1;i<N;i++){p[i]=i;}for(int i=1;i<=n;i++){int x;cin>>x;x=find(x);cout<<x<<" ";p[x]=x+1;}return 0;
}

比较幸福。直接过了。

代码

#include<bits/stdc++.h>
using namespace std;const int N=1010;int n,m;
vector<int> a[N];
int f[4][N];int main(){cin>>n>>m;for(int i=0;i<n;i++){int x;cin>>x;a[x%m].push_back(x);}memset(f,-0x3f,sizeof f);f[0][0]=0;for(int i=0;i<m;i++){sort(a[i].begin(),a[i].end());reverse(a[i].begin(),a[i].end());for(int u=0;u<3&&u<a[i].size();u++){int x=a[i][u];for(int j=3;j>=1;j--){for(int k=0;k<m;k++){f[j][k]=max(f[j][k],f[j-1][(k-x%m+m)%m]+x);}}}}cout<<f[3][0]<<endl;return 0;
}

思路

这个题题意不难，但是做法确实有点难了。

动态规划，建立一个状态转移方程，然后用贪心策略优化一下，同余的时候取一个最大的元素就可以了，可以降低时间复杂度，因为很多情况可以直接不用考虑。比较难。