题解：P13391 [GCJ 2010 #1A] Make it Smooth

Solution

考虑 dp。设

f_{i, v}

表示考虑到前

i

位最后一个保留的元素是

v

的最小代价。

删除是显然的：

f_{i, v} = \min(f_{i, v}, f_{i - 1, v} + D)

。

考虑修改为

x

，这时候要考虑与前一个像素的距离不超过

m

这一限制。那么距离超过

m

的话我们应当往前面插入若干个元素，代价即为

\mathrm{cost}(x, v) = (\lceil \frac{|x - v|}{m} \rceil - 1) \times I

。插入这部分的代价就是

f_{i - 1, v} + \mathrm{cost}(x, v)

，对于每个

x

找一个

v

使代价最小就行了，这个最小代价记作

\mathrm{minn}

。那么转移就是

f_{i, x} = \min(f_{i, x}, \mathrm{minn} + |a_i - x|)

。

最后答案就是

\min_{v = 0} ^ {255} f_{n, v}

。

注意特判一下

m = 0

的情况即可。

Code

在这

CPP

// Problem: P13391 [GCJ 2010 #1A] Make it Smooth
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P13391
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define ls x << 1
#define rs x << 1 | 1

using namespace std;

const int maxn = 105 ;
const int maxd = 255 ;
const int inf = 4e18 ;

int D, I, m, n, a[maxn] ;
int dp[maxn][260] ;

int cost(int x, int v) {
	if(m == 0) {
		if(x == v) return 0 ;
		else return inf ;
	}
	int d = llabs(x - v) ;
	int ans = (ceil(1.0 * d / m) - 1) * I ;
	ans = max(ans, 0ll) ;
	return ans ;
}

void solve(){
	cin >> D >> I >> m >> n ;
	rep(i, 1, n) {
		cin >> a[i] ;
	}
	rep(i, 1, n) {
		rep(v, 0, maxd) {
			dp[i][v] = inf ;
		}
	}
	rep(v, 0, maxd) dp[0][v] = 0 ;
	rep(i, 1, n) {
		rep(v, 0, maxd) {
			dp[i][v] = min(dp[i][v], dp[i - 1][v] + D) ;
		}
		rep(x, 0, maxd) {
			int minn = inf ;
			rep(v, 0, maxd) {
				minn = min(minn, dp[i - 1][v] + cost(x, v)) ;
			}
			dp[i][x] = min(dp[i][x], minn + llabs(a[i] - x)) ;
		}
	}
	int ans = inf ;
	rep(v, 0, maxd) {
		ans = min(ans, dp[n][v]) ;
	}
	cout << ans << endl ;
	return ;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T = 1 ; 
	cin >> T ;
	rep(i, 1, T){
		cout << "Case #" << i << ": " ;
		solve() ;
	}
	return 0 ;
}

题解：P13391 [GCJ 2010 #1A] Make it Smooth

文章操作

Solution

Code

相关推荐

评论

题解：P13391 [GCJ 2010 #1A] Make it Smooth