D - Dire Wolf (interval DP)

2014ICPC Beijing

Problem

Yes n The wolves lined up , Every time you kill a wolf, you get $a[i]$ The damage of , meanwhile , Each wolf can add $b[i]$ Point injury . Kill a wolf , The rest of the wolves automatically fill the vacancy . ask ： Kill all wolves with the least damage .

Solution

Interval merging ： Kill the second k Wolf queen , The intervals on both sides are merged .
State transition equation ：$dp[l][r]=dp[l][k-1]+dp[k+1][r]+a[k]+b[l-1]+b[r+1]$

Code

const int N = 2e2 + 5, M = 1e6 + 7;
ll a[N], b[N], f[N][N];
int main()
{
    
	IOS;
	int T, cas = 0; cin >> T;
	while (T--)
	{
    
		int n; cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		for (int i = 1; i <= n; i++)
			cin >> b[i];
		b[0] = b[n + 1] = 0;
		for (int i = 1; i <= n; i++)
			f[i][i] = b[i - 1] + b[i + 1] + a[i];
		for(int len = 2; len <= n; len++)
			for (int l = 1; l <= n - len + 1; l++)
			{
    
				int r = l + len - 1;
				f[l][r] = inf;
				for (int k = l; k <= r; k++)
					f[l][r] = min(f[l][r], f[l][k - 1] + f[k + 1][r] + a[k] + b[l - 1] + b[r + 1]);
			}

		cout << "Case #" << ++cas << ": ";
		cout << f[1][n] << endl;
	}


	return 0;
}

Rethinking

The key is how to merge intervals , I didn't figure out how to merge during the game , I have been writing greedy writing . A lot of time is wasted , Finally, I've been killing time , There is no patience to continue sitting .