11-10 21:21 太原科技大学 算法工程师 发布于山西
关注
求各位大佬指点指点，为啥ac不了？
#include
using namespace std;
#define N 3005
long long a[N],f[N][N];//dp数组，dp[i][j]表示前i个数中除以k的余数为j的当前最大和
int n,k;
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i ++) {cin >> a[i];}
memset(f,-0x3f,sizeof f);
long long maxv = -0x3f3f3f3f;
f[0][0] = 0;
for(int i = 1; i <= n; i ++){
for(int j = 0; j < k; j ++){
f[i][j] = max(f[i - 1][(j - a[i] + k) % k] + a[i],f[i - 1][j]);
//能ac的状态方程： f[i][(j + a[i]) % k] = max(f[i - 1][j] + a[i],f[i - 1][(j + a[i]) % k]);
}
}
for(int i = 1; i <= n; i ++) maxv = max(maxv,f[i][0]);
if(maxv > 0)cout << maxv << endl;
else cout << -1 << endl;
return 0;
}
using namespace std;
#define N 3005
long long a[N],f[N][N];//dp数组，dp[i][j]表示前i个数中除以k的余数为j的当前最大和
int n,k;
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i ++) {cin >> a[i];}
memset(f,-0x3f,sizeof f);
long long maxv = -0x3f3f3f3f;
f[0][0] = 0;
for(int i = 1; i <= n; i ++){
for(int j = 0; j < k; j ++){
f[i][j] = max(f[i - 1][(j - a[i] + k) % k] + a[i],f[i - 1][j]);
//能ac的状态方程： f[i][(j + a[i]) % k] = max(f[i - 1][j] + a[i],f[i - 1][(j + a[i]) % k]);
}
}
for(int i = 1; i <= n; i ++) maxv = max(maxv,f[i][0]);
if(maxv > 0)cout << maxv << endl;
else cout << -1 << endl;
return 0;
}
全部评论
相关推荐
11-07 18:40
厦门大学嘉庚学院 用户运营 点赞 评论 收藏
分享
点赞 评论 收藏
分享
投递完美世界等公司10个岗位 >
查看18道真题和解析