Codeforces Round #318 D. Bear and Blocks DP

2410 단어 트럼프를 하다
dp[i]는 i열이 제거되는 데 필요한 조작 횟수를 나타내고 dp[i]=min(i, n-i, h[i], dp[i-1]+1, dp[i+1]+1), i, n-i는 가장자리 1열을 제거할 때마다 i열에 이르는 상황, h[i]는 맨 끝을 0까지 제거하는 상황, dp[i-1]+1과 dp[i+1]+1은 좌우 양측을 제거하고 다시 한 번 i열을 제거하는 상황, 앞의 3개가 읽을 때
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define pb push_back
#define mk make_pair
#define ll long long
#define ull unsigned long long
#define pii pair
#define mk make_pair
#define fi first
#define se second
#define ALL(A) A.begin(), A.end()
#define rep(i,n) for(int (i)=0;(i)=0;(i)--)
#define repab(i,a,b) for(int (i)=(int)(a);(i)<=(int)(b);(i)++)
#define reprab(i,a,b) for(int (i)=(int)(a);(i)>=(int)(b);(i)--)
#define sc(x) scanf("%d", &x)
#define pr(x) printf("x:%d
", x) #define fastio ios::sync_with_stdio(0), cin.tie(0) #define frein freopen("in.txt", "r", stdin) #define freout freopen("out.txt", "w", stdout) #define freout1 freopen("out1.txt", "w", stdout) //#define lb puts("") #define lson ((rt<<1)+1) #define rson ((rt<<1)+2) #define mid ((l+r)/2) #define lmid (l+(r-l)/3) #define rmid (r-(r-l)/3) #define debug cout< const double PI = 3.1415926535897932384626433; const ll mod = 1e9+7; const int INF = 0x3f3f3f3f; const double eps = 1e-12; template T gcd(T a, T b){if(!b)return a;return gcd(b,a%b);} const int maxn = 2e5+10; int n, m, g, h[maxn], dp[maxn]; int main() { //frein; //freout; cin >> n; for(int i = 1; i <= n; i++){ sc(h[i]); dp[i] = min(i, n-i+1); dp[i] = min(dp[i], h[i]); } dp[0] = dp[n+1] = INF; for(int i = 1; i <= n; i++){ dp[i] = min(dp[i], dp[i-1]+1); } int ans = -1; for(int i = n; i >= 1; i--){ dp[i] = min(dp[i], dp[i+1]+1); ans = max(ans, dp[i]); } cout << ans << endl; return 0; }

초치로 설정하면 dp[i-1]+1은 왼쪽에서 오른쪽으로 한 번 뛰고, dp[i+1]+1은 오른쪽에서 왼쪽으로 한 번 뛴다.

좋은 웹페이지 즐겨찾기