?? washing clothes[pku 3211].cpp
字號:
// 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());
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -