原创
原题:
动态规划解题,先将数据分组,彼此相差k的数据为一组,这样组与组之间的数据不会受到影响,
只要从每组中选择出最大在线人数,累加起来即可。
每个数据只能有选择与不选择两种可能,设dp[i-1]存储前i-1个数据(包括第i-1个数据)中能选择的最大人数,则选择
第i个数据后dp[i]=dp[i-2]+value[i],不选择dp[i]=dp[i-1](因为不选择你只能继承),所以得出状态转移方程:
dp[i]=max[dp[i-2]+value[i],dp[i-1]);
k=0时特别处理!
java ac
1 import java.util.*; 2 3 public class main { 4 5 static int n; 6 static int k; 7 8 public static void main(string[] args) { 9 scanner reader=new scanner(system.in); 10 n=reader.nextint(); 11 k=reader.nextint(); 12 int result=0; 13 int score[]=new int[100005]; 14 int dp[]=new int[100005]; 15 int max=0; 16 for(int i=0;i<n;i++) { 17 int temp=reader.nextint(); 18 if(temp>max) { 19 max=temp; 20 } 21 score[temp]++; 22 } 23 if(k==0) { 24 for(int i=0;i<=max;i++) { 25 if(score[i]!=0) { 26 result++; 27 } 28 } 29 system.out.println(result); 30 return; 31 } 32 int value[]=new int[100005]; 33 for(int i=0;i<k;i++) { 34 int index; 35 index=0; 36 for(int j=i;j<=max;j+=k) { 37 value[index]=score[j]; 38 index++; 39 } 40 dp[0]=value[0]; 41 dp[1]=dp[0]>value[1]?dp[0]:value[1]; 42 for(int z=2;z<index;z++) { 43 dp[z]=math.max(dp[z-2]+value[z], dp[z-1]); 44 } 45 result+=dp[index-1]; 46 } 47 system.out.println(result); 48 } 49 50 }
15:53:41
2018-08-26
如对本文有疑问, 点击进行留言回复!!
荐 嵌入式linux开发环境搭建(Docker版,基于iTop 4412开发板)
SpringBoot项目部署到服务器之 Liunx环境安装jdk详细步骤
网友评论