求助,刚刚ABC,D题
  • 板块灌水区
  • 楼主Svemit
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/12/10 21:47
  • 上次更新2023/10/26 23:51:49
查看原帖
求助,刚刚ABC,D题
503792
Svemit楼主2022/12/10 21:47

一直过不了,感觉思路没问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105; 
int n,cnt,d;
int a[N];
int f[N][N][N]; //f[i][j][k]表示前i个输选j个数%D为K的最大和
inline int max(int a,int b)
{
	if(a>b)
	  return a;
	return b;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	memset(f,-1,sizeof(f));
	cin>>n>>cnt>>d;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		for(int j=i;j<=n;j++)
		{
			f[j][1][a[i]%d]=max(f[j][1][a[i]%d],a[i]);
		}  
	}
	for(int i=1;i<=n;i++)
	  for(int k=0;k<=d;k++)
	    f[i][0][k]=max(0,f[i][0][k]);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=min(i,cnt);j++)
	  {
	  	for(int k=0;k<d;k++)
	  	{
	  		f[i][j][k]=f[i-1][j][k];
	  		for(int l=j;l<=i;l++)
	  		{
	  			if(f[l-1][j-1][(k-a[l]+d)%d]==-1) continue;
	  			f[i][j][k]=max(f[l-1][j-1][(k-a[l]+d)%d]+a[l],f[i][j][k]);
			}
		}
	  }
	cout<<f[n][cnt][0];
	return 0;
}

2022/12/10 21:47
加载中...