外卖节即将过去了,小美还有很代金券没有消费掉,美团面向小美这样的用户推出了一个新的活动,即代金券消消乐活动。系统会把小美的代金券打乱顺序排成一排,小美可以进行任意多次如下操作:
如果存在相邻的两个代金券金额相等,设其面额为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}
#include<stdio.h> int * fun(int num,int quan[]) {//排序 int i, j; for (i = 0; i < num; i++) for (j = num - 1; j > 0; j--) { if (quan[num - 1] < quan[num - 2]) { int temp = quan[num - 1]; quan[num - 1] = quan[num - 2]; quan[num - 2] = temp; } } return quan; } int fun2(int num,int quan[]) { int i, j; int count = 0; int jishu; do { jishu = 0; for (i = 0; i < num - 1; i++) if (quan[i] == quan[i + 1] && quan[i] != 0) { jishu++; quan[i]++; i++; quan = fun(num, quan); } count += jishu; } while (jishu != 0); return count; } int main() { int num; int *r; scanf("%d", &num); int quan[num]; for (int m = 0; m < num; m++) scanf("%d", &quan[m]); r = fun(num, quan); printf("%d", fun2(num,r)); }只跑出来9个例子,但是不知道哪里错误了,希望有人能给我解答一下
#include <bits/stdc++.h> using namespace std; int n, x; int main() { ios::sync_with_stdio(false); cin >> n; stack<int> s; int ans = 0; while (n--) { cin >> x; while (!s.empty() && s.top() == x) { s.pop(); ans++; x++; } s.push(x); } cout << ans; return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Stack; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String[] strArr = br.readLine().trim().split(" "); Stack<Integer> stackLeft = new Stack<>(); Stack<Integer> stackRight = new Stack<>(); for(int i = 0; i < n; i++) stackLeft.push(Integer.parseInt(strArr[i])); stackRight.push(stackLeft.pop()); int money = 0; while(!stackLeft.isEmpty()){ while(stackLeft.peek() == stackRight.peek()){ int x = stackLeft.pop() + 1; // 得到新的代金券值 stackRight.pop(); money ++; if(!stackRight.isEmpty()){ while(!stackRight.isEmpty() && stackRight.peek() == x){ x = stackRight.pop(); x ++; money ++; } stackRight.push(x); }else stackRight.push(x); } stackRight.push(stackLeft.pop()); } System.out.println(money); } }
#include<bits/stdc++.h> namespace MY_DEFINE { #define ll long long #define ull unsigned long long #define db double #define rep(x, a, b) for(int (x)=(a);(x)<=(b);(x)++) #define per(x, a, b) for(int (x)=(a);(x)>=(b);(x)--) #define reP(x, a, b) for(int (x)=(a);(x)<(b);(x)++) #define Per(x, a, b) for(int (x)=(a);(x)>(b);(x)--) #define scf(a) scanf("%d",&(a)) #define scfll(a) scanf("%lld",&(a)) #define ptf(a) printf("%d",a) #define ptfll(a) printf("%lld",a) #define ptfsp(a) printf("%d ",a) #define ptfllsp(a) printf("%lld ",a) #define pli(a, b) make_pair(a,b) #define pb push_back #define pYES puts("YES") #define pNO puts("NO") #define pYes puts("Yes") #define pNo puts("No") #define pYN(flag) puts((flag)?"YES":"NO") #define pyn(flag) puts((flag)?"Yes":"No") #define el puts("") #define FS first #define SE second #define FAST_CIN_COUT ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); [[maybe_unused]] std::mt19937 rnd(time(nullptr)); } using namespace std; using namespace MY_DEFINE; const int maxn = 5e2 + 5; const int mod = 1e9 + 7; namespace MOD_CALC { inline int sub(int a, int b, int M = mod) { a -= b; if (a < 0) a += M; return a; } inline int Plus(int a, int b, int M = mod) { a += b; if (a >= M) a -= M; return a; } inline int mul(int a, int b, int M = mod) { return (int) (1ll * a * b % M); } inline int qpow(int a, int n, int M = mod) { int ans = 1, b = a; while (n) { if (n & 1) ans = mul(ans, b, M); b = mul(b, b, M); n >>= 1; } return ans; } inline int Div(int a, int b, int M = mod) { return (int) (1ll * a * qpow(b, M - 2) % M); } } using namespace MOD_CALC; int a[maxn], f[maxn][maxn], c[maxn][maxn], g[maxn]; signed main() { int n; scf(n); rep(i, 1, n) { scf(a[i]); f[i][i] = a[i]; } rep(len, 2, n) { rep(i, 1, n) { int j = i + len - 1; rep(k, i, j - 1) { if (f[i][k] && f[k+1][j] && f[i][k] == f[k + 1][j] && c[i][k] + c[k + 1][j] + 1 >= c[i][j]) { f[i][j] = f[i][k] + 1; c[i][j] = c[i][k] + c[k + 1][j] + 1; } } } } rep(i, 2, n) { rep(j, 0, i - 1) { if (f[j + 1][i]) { g[i] = max(g[i], g[j] + c[j + 1][i]); } } } cout << g[n]; }
public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); Node head=new Node(-1); Node tem=head; //临时,不用head直接 while(sc.hasNext()){ tem.next=new Node(sc.nextInt()); tem=tem.next; } Node cur=head.next; int res=0; boolean flag=true; while(true){ //多次遍历,有可能前一位的和当前的相等了 cur=head.next; //重置 flag=true; while(cur.next!=null){ //一次遍历 if(cur.value==cur.next.value){ cur.value++; cur.next=cur.next.next; res++; flag=false; }else{ cur=cur.next; } } if(flag==true) break; //没有兑换的一趟可退出了 } System.out.println(res); } static class Node{ Node next; int value; Node(int value){ this.value=value; } }
使用单栈模拟消费券合成的过程 while True: try: num = int(input()) elements = list(map(int,input().split())) stack = [] ans = 0 for ele in elements: if len(stack)==0: stack.append(ele) else: while ele == stack[-1]: ans += 1 stack.pop() ele += 1 if len(stack)==0: break stack.append(ele) print(ans) except: break
n=int(input()) an=list(map(int, input().strip().split())) stack=[] res=0 for num in an: if not stack&nbs***bsp;stack[-1]!=num: stack.append(num) else: while stack and num==stack[-1]: stack.pop() num+=1 res+=1 stack.append(num) print(res)
利用栈,每一个数x和栈顶元素相同则弹出,将x=x+1继续与栈顶元素比较,直到不等时入栈。 每弹出一次结果加一。
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); } }没有用动态规划,但是也都成功了。有没有人觉得代码有逻辑错误?
#include <iostream> #include <vector> using namespace std; int n,b,ans=0; void uni(int l,int r,vector<int>& nums){ if(l>=r) return; for(int i=l;i<r;++i){ if(nums[i]==nums[i+1]){ // cout<<nums[i]<<" "<<nums[i+1]<<endl; ans++; nums[i]+=1; nums[i+1]+=1; if(i-1>0&&nums[i-1]==nums[i]) uni(l,i,nums); if(i+2<r&&nums[i+2]==nums[i+1]) uni(i+1,r,nums); } } } int main() { vector<int> nums; cin>>n; for(int i=0;i<n;++i){ cin>>b; nums.push_back(b); } uni(0,n-1,nums); cout<<ans<<endl; return 0; } // 64 位输出请用 printf("%lld")过了70%不知道错在哪求指点
暴力求所有最后能合成一够合成一个数的所有区间,最后dp求从这些区间中最少使用几个能覆盖 满1-n整个区间,求出来的结果就是剩下的代金券数,用n减去代金券数就是答案#include<bits/stdc++.h> using namespace std; #define lowbit(x) x&(-x) #define f(i,c,d) for(int i=c;i<d;i++) #define debug(a) cout << #a: << a << endl; #define ios ios::sync_with_stdio(false);cin.tie(0); #define INF 0x3f3f3f3f #define pii pair<int,int> #define ll long long inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } const int N = 2e5+5; vector<pair<int,int> > b[1500],all; void push(int x,int y,int v){ //x左区间,y右区间,v区间值 for(auto it: b[v]){ if(it.first == y+1){ push(x,it.second,v+1); } if(x == it.second +1){ push(it.first,y,v+1); } } b[v].push_back({x,y}); all.push_back({x,y}); } int main(){ int n; cin>>n; vector<int> a(n+5); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ //递归暴力求所有最后能合成一个数的区间 push(i,i,a[i]); } //线性dp求最小能覆盖1-n的区间数 int dp[505]; memset(dp,INF,sizeof dp); dp[0]=0; sort(all.begin(),all.end()); for(auto it: all){ int x = it.first; int y = it.second; dp[y] = min(dp[y],dp[x-1]+1); } cout<<dp[n]<<endl; return 0; }
#include <iostream> using namespace std; /* dp[i,j) 表示对 arr[i,j)进行合并可以产生的尽量多的奖励金。 combine[i,j) 表示 arr[i,j)能否通过某种顺序合并为一个元素,如果可以该元素就是combine[i,j),否则combine[i,j)==0 (如果arr[i,j)能合并为一个元素,则该元素一定是唯一的:可以这样来考虑这件事情,假设arr[i,j)最小的元素为k,则我们不关心 具体是怎么合并的,但所有的k一定通过合并变为k+1,实际上,我们总可以先把所有的k消掉。接着,剩余的最小元素为k+1,... 如此下去, 每一轮中,arr[i,j)中最小元素的个数都是确定的,arr[i,j)中本来的元素个数也是确定的,因此,最终可以合并成的那个元素也是确定的) 那么 combine[i,j) == if exists {i+1<=k<j} s.t. combine[i,k) == combine[k,j) != 0 then combine[i,k)+1 else 0 dp[i,j) = if combine[i,j) != 0 then j-i-1 (如果能全部合并,肯定是全部合并最划算,因为消掉的元素最多) else max{i+1<=k<j}(dp[i,k)+dp[k,j) */ int dp[503][503]; int combine[503][503]; // int nodes[503]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>combine[i][i+1]; for(int len = 2;len<=n;len++){ for(int i=1;i<=n+1-len;i++){ int j = i+len; int k = 0; for(k=i+1;k<j;k++){ if(combine[i][k]!=0&&combine[i][k]==combine[k][j]) break; } if(k<j) combine[i][j] = combine[i][k]+1; else combine[i][j] = 0; } // combine for(int i=1;i<=n+1-len;i++){ int j = i+len; if(combine[i][j]!=0){ dp[i][j] = len-1; continue; } for(int k=i+1;k<j;k++){ dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]); } } } cout<<dp[1][n+1]; } // 64 位输出请用 printf("%lld")
import java.util.Scanner; import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int n = in.nextInt(); LinkedList<Integer> num = new LinkedList<Integer>(); int flag = 1; int ans = 0; for(int i = 0; i < n; i++) { num.add(in.nextInt()); } while(flag != 0) { flag = 0; for(int i = 0; i < num.size() - 1; i++) { if(num.get(i) == num.get(i + 1)) { flag = 1; ans++; num.remove(i + 1); num.set(i, num.get(i) + 1); break; } } } System.out.println(ans); } }
直接判断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); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] dp = new int[n + 1][n + 1]; int[][] w = new int[n + 1][n + 1]; for (int i = 1; i <= n; i++) { dp[i][i] = 1; w[i][i] = sc.nextInt(); } // 初始化 dp[i][j] 的区间长度 for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { dp[i][j] = j - i + 1; } } // len 表示遍历的长度,依次从这些长度中去更新区间最小长度 for (int len = 1; len <= n; len++) { for (int i = 1; i + len <= n ; i++) { for (int j = i; j <= i + len -1; j++) { dp[i][len + i] = Math.min(dp[i][len + i], dp[i][j] + dp[j + 1][i +len]); if(dp[i][j] == 1 && dp[j + 1][i + len] == 1 && w[i][j] == w[j + 1][i + len]){ dp[i][i + len] = 1; w[i][i + len] = w[i][j] + 1; } } } } // System.out.println(dp[1][n]); System.out.println(n - dp[1][n]); } } |