unique solution[pku 2889].cpp

PKU 上的几个题目 Tunnel Warfare Unique Solution Washing Clothes Weather Forecast Who Gets the Most Ca

// PKU 2889
// O(N^2) DP with save path
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int NMAX = 1010;
int n, m;
int dp[2][NMAX][2];
bool path[2][NMAX][2];
int now, pre;
int num[NMAX];

bool solve()
{
	int i, j;
	
	for (i=0; i<=n; i++)
		dp[0][i][0] = dp[0][i][1] = path[0][i][0] = path[0][i][1] = 0;
	
	pre = 0;
	now = 1;
	for (i=1; i<=m; i++)
	{
		dp[now][i][0] = INT_MIN;
		path[now][i][0] = false;

		dp[now][i][1] = dp[pre][i][0];
		path[now][i][1] = path[pre][i][0];
		dp[now][i][1] += num[i];
		for (j=i+1; j<=n; j++)
		{
			if (dp[now][j-1][0] > dp[now][j-1][1])
			{
				dp[now][j][0] = dp[now][j-1][0];
				path[now][j][0] = path[now][j-1][0];
			}
			else if (dp[now][j-1][0] == dp[now][j-1][1])
			{
				dp[now][j][0] = dp[now][j-1][0];
				path[now][j][0] = true;
			}
			else
			{
				dp[now][j][0] = dp[now][j-1][1];
				path[now][j][0] = path[now][j-1][1];
			}
			
			if (dp[now][j-1][1] > dp[pre][j][0])
			{
				dp[now][j][1] = dp[now][j-1][1];
				path[now][j][1] = path[now][j-1][1];
			}
			else if (dp[now][j-1][1] == dp[pre][j][0])
			{
				dp[now][j][1] = dp[now][j-1][1];
				path[now][j][1] = true;
			}
			else
			{
				dp[now][j][1] = dp[pre][j][0];
				path[now][j][1] = path[pre][j][0];
			}
			dp[now][j][1] += num[j];
		}
		now ^= 1;
		pre ^= 1;
	}
	
	//cout << dp[m][n][0] << ", " << dp[m][n][1] << endl;
	int flag = (dp[pre][n][1] > dp[pre][n][0]) ? 1 : 0;
	
	if (n>m && dp[pre][n][1] == dp[pre][n][0])
		return false;
	else if (n == m)
		flag = 1;
	return !path[pre][n][flag];
}

int main()
{
	int i, j;
	while (scanf("%d %d", &n, &m), n|m)
	{
		for (i=1; i<=n; i++)
			scanf("%d", num+i);
		puts(solve() ? "Yes" : "No");
	}
}