0分求助
  • 板块P1929 迷之阶梯
  • 楼主Kalium
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/7/26 09:34
  • 上次更新2023/11/4 13:18:19
查看原帖
0分求助
328170
Kalium楼主2021/7/26 09:34
#include <iostream>
#include <cstdio>
#include <cstring>

#define ll long long
#define inf 1e18

using namespace std;

int n;

ll dp[207];

ll a[207];

inline ll mina(ll a, ll b) {
	if (a < b)
		return a;
	return b; 
}

int main() {
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i ++)
		scanf("%lld", &a[i]);
	
	dp[0] = dp[1] = 0;
	
	for (int i = 2; i <= n; i ++) dp[i] = inf;
	
	for (int i = 2; i <= n; i ++) {
		
		if (a[i] == a[i - 1] + 1) dp[i] = dp[i - 1] + 1;
		else {
			for (int j = i - 1; j >= 1; j --) {
				for (int k = j - 1; k >= 1; k --) {
					
					if (a[i] <= a[k] + (1 << (j - k))) {
						dp[i] = mina(dp[i], dp[k] + ((j - k) << 1) + 1);
						//cout << i << " " << j << " " << k << " " << dp[i] << endl;
					}
				}
			}
		}
	}
	
	if (dp[n] == inf) printf("-1\n");
	else printf("%lld\n", dp[n]);
	
	return 0;
} 

亲测样例已过,硬是看不出问题

2021/7/26 09:34
加载中...