朴素做法三维dp(MLE)
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=1e3+10;
int n,t;
ll dp[N][4][M];//表示从前i个物品中选,选j个,且总和模t等于k(属性:最大值)
int main()
{
cin>>n>>t;
memset(dp,-0x3f,sizeof dp);
for(int i=0;i<=n;i++)
dp[i][0][0]=0;
for(int i=1;i<=n;i++)
{
int v;
cin>>v;
for(int j=1;j<4;j++)
for(int k=0;k<t;k++)
{
dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-1][((k-v)%t+t)%t]+v);
}
}
cout<<dp[n][3][0];
return 0;
}
滚动数组优化到二维,TLE(时间复杂度依然很大,只能过8个数据)
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10,M=1e3+10;
int n,t,dp[4][M],v[N];//观察转移方程只与上一层有关,所以遍历j也要从后往前遍历
int main()
{
cin>>n>>t;
memset(dp,-0x3f,sizeof dp);
for(int i=1;i<=n;i++)
cin>>v[i];
dp[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=3;j>=1;j--)
for(int k=0;k<t;k++)
dp[j][k]=max(dp[j][k],dp[j-1][((k-v[i])%t+t)%t]+v[i]);
cout<<dp[3][0];
return 0;
}
最终优化版(对模m的数进行分类,因为最多取三个数,因此只遍历前三个数就行了)
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n,m,dp[4][N];
vector <int>a[N];
bool cmp(int a,int b)//按从大到小进行排序,进行遍历每一类的前三个数,因此要自定
{
return a>b;//比较函数
}
int main()
{
cin>>n>>m;
memset(dp,-0x3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x%m].push_back(x);//对模m的结果进行分类
}
for(int i=0;i<m;i++)
{
sort(a[i].begin(),a[i].end(),cmp);
for(int u=0;u<3&&u<a[i].size();u++)
for(int j=3;j>=1;j--)
for(int k=0;k<m;k++)
dp[j][k]=max(dp[j][k],dp[j-1][((k-a[i][u])%m+m)%m]+a[i][u]);
}
cout<<dp[3][0];
return 0;
}