C 解法, 执行用时: 250ms, 内存消耗: 98416K, 提交时间: 2022-01-03 11:24:46

#include<stdio.h>
#include<string.h>
int dp[5005][5005];
int max(int a, int b) {
	return (a > b) ? a : b;
}
int main(void)
{
	int n;
	scanf("%d", &n);
	int w[5005];
	for (int i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
	}
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= n; i++) {
            for(int j=0;j<n;j++){
        dp[i][j]=dp[i-1][j];
    }
			for (int j = 0; j < n; j++) {
				if (dp[i][w[i] % n] == 0)dp[i][w[i] % n]++;
				if(dp[i-1][j]!=0) {
					dp[i][(j + w[i] % n) % n] = max(dp[i - 1][j] + 1, dp[i - 1][(j + w[i] % n) % n]);
				}
			}
		}
    for(int i=1;i<=n;i++){
    int ans=0;
    for(int j=0;j<n;j++){
        if((j*i)%n==0)ans=max(ans,dp[n][j]);
    }
    printf("%d ",ans);
}
	return 0;
}

C++ 解法, 执行用时: 199ms, 内存消耗: 98476K, 提交时间: 2022-01-02 12:13:28

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[5005][5005];
int a[5005]; 
int main(){
cin>>n;
for(int i=1;i<=n;i++){
	scanf("%d",&a[i]);
}
memset(dp,-0x3f,sizeof(dp));
dp[1][a[1]]=1;
dp[1][0]=0;
for(int i=2;i<=n;i++){
	for(int j=0;j<n;j++){
		dp[i][j]=dp[i-1][j];
	}
	for(int j=0;j<n;j++){
		dp[i][(j+a[i])%n]=max(dp[i][(j+a[i])%n],dp[i-1][j]+1);
	}
}
for(int i=1;i<=n;i++){
	int ans=0;
	for(int j=0;j<n;j++){
		if((j*i)%n==0)ans=max(ans,dp[n][j]);
	}
	printf("%d ",ans);
}








	return 0;
}