题目传送门

这是一个经典的游戏--2048,没玩过的人可以去玩一玩--又一个传送门.

【问题分析】

这是一个简化版的2048,因为它只是线性结构，而不是二维结构.另外,只有相邻且相等的两个才能合并,且合并后得到的数字并非翻倍而是+1,如9与9合并为10.看到这道题首先想到了区间dp，但经过我的一通瞎搞仔细分析，发现没学过dp的人也能做出来--模拟大法.这题模拟的算法不会超时且它的时间复杂度(n * n)甚至比dp(n * n * n)还快.（其实是看到大佬们用的都是dp，本蒟蒻的dp过于...）

基本思路就是从数字小的开始合并.首先我们知道最后它不一定会合并成一个数字,但最多只会合并n-1次.所以我们要先在外面套一层1_{n-1的大循环.接着可以分析出当合并到第i次的时候,又n-i+1个数字,所以最外面的一层循环可以从n}2,方便.

	for(int i=n;i>1;--i){
		
	}

接着在每次循环都找到相连在一起的相同的且和最小的两个数,将前一个记为id(后一个记为id+1).

	int minn=1e9;
	int id;
	for(int j=1; j<=i; ++j) {
		if(a[j]==a[j+1]&&a[j]<=minn) {
			minn=a[j];
			id=j;
		}
	}

然后我们就可以把两个数字合并后的值(存在了minn里面)存入a[id]里面,并把它后面的全部向前位移一位.

	a[id]=minn+1;
	for(int j=id+1; j<=i; ++j) {
		a[j]=a[j+1];
		a[j+1]=0;
	}

这里有个要点,如果寻找一遍后没有找到相连且相等的数对,则要终止循环.所以可以先将id赋值为0,循环一遍后若id仍为0,就终止循环.

最后我们只要再来一遍循环找到最大的那个就好了.

	int ans=0;
	for(int i=1; i<=n; ++i) {
		if(a[i]>ans) ans=a[i];
	}
	printf("%d",ans);

【最终代码（AC通过）】

#include
using namespace std;
int a[250];
int f[250];
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&a[i]);
	}
	for(int i=n; i>1; --i) {
		int minn=1e9;
		int id=0;
		for(int j=1; j<=i; ++j) {
			if(a[j]==a[j+1]&&a[j]<=minn) {
				minn=a[j];
				id=j;
			}
		}
		if(!id) break;
		a[id]=minn+1;
		for(int j=id+1; j<=i; ++j) {
			a[j]=a[j+1];
			a[j+1]=0;
		}
	}
	int ans=0;
	for(int i=1; i<=n; ++i) {
		if(a[i]>ans) ans=a[i];
	}
	printf("%d",ans);
	return 0;
}

到此结束，欢迎指错！