外卖节即将过去了,小美还有很代金券没有消费掉,美团面向小美这样的用户推出了一个新的活动,即代金券消消乐活动。系统会把小美的代金券打乱顺序排成一排,小美可以进行任意多次如下操作:
如果存在相邻的两个代金券金额相等,设其面额为x,小美可以使用这两张代金券换一张面额为x+1的代金券,并将其仍放在原来两张券的位置上,每进行一次这样的操作,小美就可以获得1元可以无限期使用的奖励金。
小美觉得奖励金可太香了,因此她想获得尽可能多的奖励金,请问她最多可以获得多少奖励金。
外卖节即将过去了,小美还有很代金券没有消费掉,美团面向小美这样的用户推出了一个新的活动,即代金券消消乐活动。系统会把小美的代金券打乱顺序排成一排,小美可以进行任意多次如下操作:
如果存在相邻的两个代金券金额相等,设其面额为x,小美可以使用这两张代金券换一张面额为x+1的代金券,并将其仍放在原来两张券的位置上,每进行一次这样的操作,小美就可以获得1元可以无限期使用的奖励金。
小美觉得奖励金可太香了,因此她想获得尽可能多的奖励金,请问她最多可以获得多少奖励金。
输入第一行仅包含一个正整数n,表示小美拥有的代金券数量。(1<=n<=500)
输入第二行包含n个正整数,每个整数x表示一张代金券的面额,同时这也是系统排出的代金券顺序。(1<=x<=100)
输出仅包含一个整数,表示小美最多可以获得的奖励金数量。
5 1 1 1 1 1
3
{1,1,1,1,1}->{1,1,1,2}->{1,2,2}->{1,3}
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner =new Scanner(System.in); int n =scanner.nextInt(); int[] nums =new int[n]; for (int i = 0; i < n; i++) { nums[i] =scanner.nextInt(); } int res=0; for (int j = 1; j < n; j++) { if(nums[j-1]==nums[j]){ res++; nums[j]=nums[j-1]+1; nums[j-1]=-1; for (int k = j-1; k >=0 ; k--) { if(nums[k]!=-1){ if(nums[j]==nums[k]){ res++; nums[j]=nums[j]+1; nums[k]=-1; }else { break; } } } } } System.out.println(res); } }没有用动态规划,但是也都成功了。有没有人觉得代码有逻辑错误?
直接判断nums[index] he nums[index+1]相不相等,不相等index++,相等将nums[index]++, 并将数组的右边的所有值左移(arraycopy不会太慢)然后将index回溯一个(不为0的时候),再继续匹配。实际上本来应该用双向链表做的,这里是用数组模拟。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] nums = new int[n]; for (int i=0; i<n; i++) { nums[i] = in.nextInt(); } int index = 0; int end = n-1; int mergeTimes = 0; while(index < end) { if (nums[index] != nums[index+1]) { index++; continue; } nums[index] = nums[index] + 1; if (index < end -1) { System.arraycopy(nums, index+2, nums, index+1, end-(index+1)); // end--;就可以了,将nums[end]设为零主要是调试好看 nums[end--] = 0; } if (index > 0) { index--; } mergeTimes++; } System.out.println(mergeTimes); } }
import java.io.*; import java.util.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.valueOf(br.readLine()); String[] s=br.readLine().split(" "); Stack<Integer> stack=new Stack<>(); stack.push(Integer.valueOf(s[0])); int res=0; for(int i=1;i<n;i++){ int tmp=Integer.valueOf(s[i]); while(stack.size()!=0 && tmp==stack.peek()){ res++; stack.pop(); tmp++; } stack.push(tmp); } System.out.println(res); } }一个栈搞定
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[]a = new int[n]; for(int i=0;i<n;i++){ a[i] = sc.nextInt(); } System.out.println(n-helper(a)); } public static int helper(int[]a){ if(a.length<=1) return a.length; int p = Integer.MAX_VALUE; int m =Integer.MAX_VALUE; int n = a.length; for(int i=0;i<n;i++){ m = Math.min(m,a[i]); } int j = -1; int k = 0; for(int i=0;i<n;i++){ if(a[i]==m&&j==-1){ j = i; k = j; while(k+1<n&&a[k+1]==m){ k++; } break; } } int t = k-j+1; if(t%2==0){ int[]b = new int[n-t/2]; for(int i=0;i<j;i++){ b[i] = a[i]; } for(int i=j;i<j+t/2;i++){ b[i] = m+1; } for(int i=j+t/2;i<n-t/2;i++){ b[i] = a[i+t/2]; } p = Math.min(p,helper(b)); } else{ for(int q=0;q<=t/2;q++){ int[]b = new int[j+q]; int[]c = new int[n-k-1+t/2-q]; for(int i=0;i<j;i++){ b[i] = a[i]; } for(int i=j;i<j+q;i++){ b[i] = m+1; } for(int i=0;i<t/2-q;i++){ c[i] = m+1; } for(int i=t/2-q;i<n-k-1+t/2-q;i++){ c[i] = a[i+k+1-t/2+q]; } p = Math.min(p,helper(b)+helper(c)+1); } } return p; } }