自动搬运

查看原文

来自洛谷，原作者为

	stansxt 人世间 有百媚千红 我独爱 爱你那一种

搬运于2025-08-24 21:31:01，当前版本为作者最后更新于2020-05-24 15:40:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

• 感觉其它大佬的题解都不是很友善呢~

• 所以这里我主要讲下dp的设计和转移，然后附上窝的代码QwQ

思路

• 一眼dp。
• s代表的是所有数的和，k是个数。所以让每个数都减一，然后求和就直接是s-k了。
• 从前面删和从后面删是没有本质区别的，因为最终要求删完。
• 注意到如果两个数列同时删超过1个数，比如$a$中$a_i,a_j$，设删掉的b中元素的和为$b_{sum}$，那么对答案的贡献就是$(a_i+a_j)\times b_{sum}$，它与$a_i\times b_{sum}+a_j\times b_{sum}$是相等的。所以每次至多有一个数列删去超过一个数。
• 看上去是个类似匹配dp的东西。所以设计$dp[i][j]$表示$a$数列删去i个数，b数列删去j个数，此时答案的最小值。
• 对于$dp[i][j]$，那么有三种情况：
  • $a$数列仅删去$a_i$，b数列仅删去$b_j$，那么就是$dp[i-1][j-1]+a[i]\times b[j]$
  • $a$数列删去$a_i$的时候b数列同时删去$b_j$和之前连续的一段数（$b_{j-1}, b_{j-2},……,b_{k}$），那么就是$dp[i-1][k-1]+a_i\times\Sigma_{x=k}^j{b_x}$，由于$a_i\times\Sigma_{x=k}^{j-1}{b_x}$已经更新过$dp[i][j-1]$，所以也即是$dp[i][j-1]+a[i]\times b[j]$。
  • 同理，还有一个是$dp[i-1][j]+a[i]\times b[j]$。
• 然后就完啦，$O(n^2)$直接转移即可。

代码

//P1846 游戏
//submit 1
//By sxt on 2020.5.23
#include<bits/stdc++.h>

#define rg register int
#define il inline
#define in read()
#define _num(x) (x >= '0' && x <= '9')
#define ql(x) memset(x, 0, sizeof(x)) 
#define mid (l+r>>1)
#define min(x, y) (x<y?x:y)
#define Min(x, y, z) min(x, min(y, z))

using namespace std;

const int N = 2007; 

il int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!_num(ch)){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(_num(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

char f[10];
int pcnt;

il void pint(int x){
	pcnt = 0;
	if(x == 0) putchar('0');
	while(x){
		f[++pcnt] = x % 10 + '0';
		x /= 10;
	}
	while(pcnt) putchar(f[pcnt--]);
	putchar('\n');
}

int b[N], a[N], dp[N][N], n, m;

signed main()
{
	n = in, m = in;
	for(rg i = 1; i <= n; ++ i)a[i] = in, --a[i];
	for(rg i = 1; i <= m; ++ i)b[i] = in, --b[i];
	memset(dp, 0x3f3f3f, sizeof(dp));
	dp[0][0] = 0;
	for(rg i = 1; i <= n; ++ i)for(rg j = 1; j <= m; ++ j)
		dp[i][j] = Min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + a[i] * b[j];
	pint(dp[n][m]);
	return 0;
}

The · End.