washing clothes[pku 3211].cpp

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

// PKU 3211
// DP
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

typedef unsigned long UL;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> VI;

#define foreach(it,c) for (it=(c).begin(); it!=(c).end(); it++)

const int MMAX = 11;
const int NMAX = 110;
const int MAX = 100100;

char col[MMAX][11];
vector <int> cloth[MMAX];
int cdiv[MMAX][2];
int n, m;
bool dp[MAX];

void add_cloth(char * p, int t)
{
	int i;
	for (i=0; i<m; i++)
		if (strcmp(p, col[i]) == 0)
		{
			cloth[i].push_back(t);
			return;
		}
}

int cal_dp(int col, int limit)
{
	int i, j;
	for (i=0; i<MAX; i++)
		dp[i] = 0;
	dp[0] = true;
	for (i=0; i<cloth[col].size(); i++)
	{
		int mi = cloth[col][i];
		for (j=limit; j>=0; j--)
		{
			if (dp[j])
				dp[j + mi] = true;
		}
	}
	for (i=limit; i>=0; i--)
		if (dp[i])
			return i;
}

int solve()
{
	int i, j, k;

	int ret = 0;
	for (i=0; i<m; i++)
	{
		int tmp = 0;
		VI::iterator iter;
		foreach(iter, cloth[i])
			tmp += *iter;
		ret += tmp - cal_dp(i, tmp>>1);
	}

	return ret;
}

int main()
{
	int i, j;
	while (scanf("%d %d", &m, &n), m|n)
	{
		for (i=0; i<m; i++)
		{
			scanf("%s", col[i]);
			cloth[i].clear();
		}
		for (i=0; i<n; i++)
		{
			int t;
			char cc[12];
			scanf("%d %s", &t, cc);
			add_cloth(cc, t);
		}
		printf("%d\n", solve());
	}
}