解题思路:
先自己用着先把,AC是AC了,可是还有一些地方有点模糊,过后看了...
去看别人的题解吧....
参考代码:
#include<bits/stdc++.h> #define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; const int maxn=100005; int n,k,max_score=INT_MIN; int ans=0; int a[maxn]= {0}; //人数 int hash_[maxn]= {0}; //分数 int dp[maxn]= {0}; //动态规划 int cnt[maxn]= {0}; //取分差用的 int main() { hh; cin>>n>>k; for(int i=0; i<n; i++) { cin>>a[i]; hash_[a[i]]++; if(max_score<a[i]) { max_score=a[i]; } } if(k==0) { //特判 for(int i=0; i<=max_score; i++) { if(hash_[i]>0) { ans++; } } cout<<ans<<endl; exit(0); //quit out } for(int i=0; i<k; i++) { int pos=0; for(int j=i; j<maxn; j+=k) { cnt[pos++]=hash_[j]; } dp[0]=cnt[0]; for(int j=0; j<pos; j++) { if(j==1) { dp[j]=max(dp[j-1],cnt[j]); } else { dp[j]=max(dp[j-1],dp[j-2]+cnt[j]); } } ans+=dp[pos-1]; } cout<<ans<<endl; return 0; }
0.0分
0 人评分