Codeforces Round #600 (Div. 2) E. Antenna Coverage（dp）

题意：

m个Antenna，每个Antenna的位置是\(x_i\)，分数是\(s_i\),覆盖范围是\([x_i - s_i; x_i + s_i]\),每个硬币可以使一个Antenna的\(s_i\)+1，求覆盖整个\([1;m]\)的最少硬币

思路：

\(f[pos][0]\)表示\([1,pos]\)没有被覆盖还要花费的最少硬币,\(f[pos][1]\)表示\([1,pos]\)被覆盖的最小花费硬币，对于每个\(pos\)枚举Antenna，有以下这几种情况

\(pos\)在\(x_i\)的右边,且Antenna\(i\)扩展到\(pos\)时的左边已经有Antenna覆盖，则Antenna\(i\)扩展到\(pos\)时\(f[pos][1] = min(f[pos][1],f[max(2*x[j]-pos-1,0)][1]+max(pos-x[j]-s[j],0));\)
\(pos\)在\(x_i\)的右边,且Antenna\(i\)扩展到\(pos\)时的左边无Antenna覆盖，则Antenna\(i\)扩展到\(pos\)时\(f[pos][1] = min(f[pos][1],f[max(2*x[j]-pos-1,0)][0]+1+max(pos-x[j]-s[j],0));\)
\(pos\)在\(x_i\)的左边,则只需扩展\(x_i\)的左侧\(f[pos][1] = min(f[pos][1],min(f[max(x[j]-s[j]-1,0)][1],f[max(x[j]-s[j],0)][0]));\)

\(f[i][1]\)和\(f[i][0]\)的区别是若左边已经有Antenna覆盖了，就可以少去覆盖\([i-1,i]\)的花费

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 200100;

int f[N][2],s[N],x[N];

int main()

{

	int n,m;

	cin >> n >> m;

	for (int i = 1; i <= m; i++) f[i][0]=i-1,f[i][1]=1<<30;

	f[0][1] = 0;

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

	 {

	 	cin >> x[i] >> s[i];

	 }

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

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

	 if ( i >= x[j])

	 {

	 	f[i][1] = min(f[i][1],f[max(2*x[j]-i-1,0)][1]+max(i-x[j]-s[j],0));

	 	f[i][1] = min(f[i][1],f[max(2*x[j]-i-1,0)][0]+1+max(i-x[j]-s[j],0));

	 }

	 else

	 {

	   f[i][1] = min(f[i][1],f[max(x[j]-s[j]-1,0)][1]);

	   f[i][1] = min(f[i][1],f[max(x[j]-s[j],0)][0]);

     }

	cout << f[m][1] << endl;

}

巴特西

Codeforces Round #600 (Div. 2) E. Antenna Coverage

Codeforces Round #600 (Div. 2) E. Antenna Coverage（dp）

题意：

m个Antenna，每个Antenna的位置是\(x_i\)，分数是\(s_i\),覆盖范围是\([x_i - s_i; x_i + s_i]\),每个硬币可以使一个Antenna的\(s_i\)+1，求覆盖整个\([1;m]\)的最少硬币

思路：

\(f[pos][0]\)表示\([1,pos]\)没有被覆盖还要花费的最少硬币,\(f[pos][1]\)表示\([1,pos]\)被覆盖的最小花费硬币，对于每个\(pos\)枚举Antenna，有以下这几种情况

\(f[i][1]\)和\(f[i][0]\)的区别是若左边已经有Antenna覆盖了，就可以少去覆盖\([i-1,i]\)的花费

代码：

最新文章

热门文章