게임

제목 링크
제목: 두 개의 정수 수열을 정하고 그것을 사용해서 게임을 해야 한다. 수열에 대해 몇 번의 조작을 해야 한다. 매번 조작할 때마다 두 개의 정수 K1과 K2를 선택하고 첫 번째 수열의 마지막 K1의 수를 삭제하고 그것들의 수열과 S1을 계산해야 한다.두 번째 수열의 마지막 K2 수를 삭제하고 그것들의 수와 S2를 계산합니다.이번 조작의 득점은 (S2-K2)*(S1-K1)이다.두 개의 수열은 동시에 비워야 하며, 한 개의 수열이 비워서는 안 되고, 다른 수열에는 몇 개의 수열이 있다.게임의 총 득점은 매번 조작의 득점 총계이다.
최소의 총득점을 구하다.
수열 길이 <=2000<=2000<=2000, 권한은 모두 정수입니다.
문제풀이: 이런 문제는 평점이 높지 않은 것 같지만, 사실 잘 풀리는 것은 아니다.일반적으로 코드가 매우 짧은 문제는 모두 사고의 난이도가 낮지 않다.
이 문제의 가장 간단한 dp 아이디어는 dp[i][j]dp[i][j]dp[i][j]는 첫 번째 수열이 후 ii개수를 고려했고 두 번째 수열은 후 jj개수의 최소 답안을 고려했다.가장 폭력적인 이동 방법은 두 수열의 이전 위치가 각각 어디에 있는지 매거하는 것이다. 이렇게 하면 O(n2∗m2)O(n^2*m^2)O(n2∗m2)의 방법을 얻을 수 있다.그러나 이 방법도 일반적인 수단으로 최적화할 수 없을 것 같다.
그러나 이 문제의 정권은 상태를 바꾸는 것이 아니라 사고방식을 바꾸는 것이다.우선 공헌 답안의 식에서 뺀 구간의 길이에 대해 우리는 두 수열에 있는 각 수의 권치를 모두 111로 바꾸면 곱셈의 분배율에 따라 곱한 후에 결과는 바뀌지 않는다.이렇게 해서 우리는 두 수열의 지난번 단점이 어디에 있는지 일일이 열거하지 않고 바로 앞의 위치에서 옮겨왔다.우리는 두 번의 합병을 고려하여 첫 번째 공헌이 a1∗b1+a2∗b2a1*b1+a2*b2a1∗b1+a2?b2라면 두 번을 합치면 공헌이 (a1+a2)?(b1+b2)(a1+a2)*(b1+b2)*(a1+b2)(a2+b2)?(b1+b2) 전자(b1+b2)이고 후자가 반드시 큰 단락일수록 우리의 답이 우수하다.양쪽의 길이가 반드시 같지 않기 때문에, 우리는 매번 반드시 한 수열에서 한 수를 선택하고, 또 다른 수열에서 연속적인 몇 수를 선택했다.그러면 우리는 이동할 때 현재 두 수열이 모두 하나의 수인지, 아니면 첫 번째 수열이 여전히 이전의 수를 사용하는지, 두 번째 수열이 계속 새로운 수를 넣는지, 아니면 첫 번째 수열이 계속 새로운 수를 넣는지, 두 번째 수열은 여전히 이전의 그 수만 선택한다.그래서 우리는 dp 방정식을 얻어냈다. dp[i] [j] [j] = mi n(dp [ii-1] [j 1] [j 1], dp [i] [i] [j] = m in(dp [iii-1] [j] [j] [j 1], dp [i] [i] [i] [i] [j] j-1], dp[i-31][j])+a[i], b[j].곱셈의 분배율에 따라 이렇게 계산하는 정확성을 보장할 수 있다.
이렇게 하면 하나의 상태수는 O(n∗m)O(n*m)O(n∗m)이고 전이 복잡도는 O(1)O(1)O(1)O(1)의 dp로 이 문제를 해결할 수 있다.
코드:

#include 
using namespace std;

int n,m,a[2010],b[2010],dp[2010][2010];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		--a[i];
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%d",&b[i]);
		--b[i];
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		dp[i][j]=min(dp[i-1][j-1]+a[i]*b[j],min(dp[i-1][j]+a[i]*b[j],dp[i][j-1]+a[i]*b[j]));
	}
	printf("%d
",dp[n][m]);
	return 0;
}