SGU 183.Painting the balls

时间限制：0.25s

空间限制:4M

题意:

　在n（n<=10000）个球中,给若干个球涂色,每个球涂色的代价为C_i,使得任意连续m（m<=100）个球中有至少两个球被涂了色.

Solution：

　首先很直接地能想到一个DP的状态转移方程

f[i][j] 代表，当前涂第i个球，且前面最近一个被涂色的球为j的最小代价

f[i][j]=min(f[j][k])+C_i, k>i+1-m

分析这个转移方程的时间复杂度是O（n*m*m）在此题的数据范围中高达10^8

显然我们需要更好的解法

分析上面的方程发现，在计算min（f[j][k]）时，是有重复计算的部分的，

于是想办法减少这个重复的过程。

对于一个 j，i的范围在（j+1，j+m-1）

对应k的范围是（i+1-m+1）~（j-1）

如果我们让i从（j+m-1）倒推至（j+1）

就可以让k从（j-1）变成（i+1-m+1）

min（f[j][k]）需要计算的范围就会依次变大，而且可以递推求出

即可以在O（1）的时间里求出min（f[j][k]）

总的时间复杂度就变成了O（n*m）

再发现空间上不能直接用n*m的数组，加上滚动数组优化就行了

code

#include <iostream>

#include <cstring>

using namespace std;

const int mod = 101;

int n, m;

int c[10009];

//f[i][j]涂当前第i个球,和第i,第j个球的最小代价

//只保留最近的200个;

int f[200][200];

int main() {

	cin >> n >> m;

	for (int i = 1; i <= n; i++) cin >> c[i];

	memset (f, 0x3f, sizeof f);

	f[1][0]=c[1];

	for (int i = 1; i <= m; i++)

		for (int j = 1; j < i; j++)

			f[i][j] = c[i] + c[j];

	for (int j = 2; j < n; j++) {

		int tem = 0x3f3f3f3f;

		for (int i = j + m - 1; i > j; i--) {

                     if(i<=m) break;

			tem = min (tem, f[j%mod][(i - m)%mod]);

			f[i%mod][j%mod] = tem + c[i];

		}

	}

	int ans = 0x7fffffff;

	for (int i = n - m + 1; i <= n; i++)

		for (int j = i - 1; i - j < m && n - j < m; j--)

			ans = min (ans, f[i % mod][j % mod]);

	cout << ans;

	return 0;

}

巴特西

SGU 183.Painting the balls

最新文章

热门文章