poj1837 Balance
IAmL
posted @ 2009年4月20日 07:34
in 解题报告
with tags
poj1837解题报告
, 4216 阅读
自从4.11在sysu预选赛充分地感觉到无力之后，有一个多星期患上了赛后综合症，一直不想或者说，逃避编程。经过啊通和龙兄的帮助，终于在一个多星期后的今天重新做了poj的题，也做了sicily的题，总算从阴影中走出。呵呵。只能怪自己太水了，差点就成了：在哪跌倒，就在哪埋了＝ ＝。
好了，废话少说，这题的主要难点是找状态存储方法（er，据说所有的dp题都是这样，所以这句有点废＝ ＝）。存储方法是m[i][t]表示有i个物品时，总权为t的个数。状态转移方程m[i][t] += m[i-1][j+hook[k]*w[i]]，最后只要找出m[g][N]的数目就可以了。
＝＝＝＝＝＝一般般的分割线＝＝＝＝＝＝
#include <iostream>
using namespace std;
#define N 7500
int m[21][15000];
int main()
{
int i, j, k, c, g, hook[21], w[21];
cin >> c >> g;
for (i = 1; i <= c; i++) cin >> hook[i];
for (i = 1; i <= g; i++) cin >> w[i];
//initilize
memset(m, 0, sizeof(m));
for (k = 1; k <= c; k++)
m[1][hook[k] * w[1] + N]++;
//dp
for (i = 2; i <= g; i++)
{
for (j = 0; j < 2 * N; j++)
{
if (m[i - 1][j] == 0) continue;
for (k = 1; k <= c; k++)
m[i][j + hook[k] * w[i]] += m[i - 1][j];
}
}
cout << m[g][N] << endl;
return 0;
}
using namespace std;
#define N 7500
int m[21][15000];
int main()
{
int i, j, k, c, g, hook[21], w[21];
cin >> c >> g;
for (i = 1; i <= c; i++) cin >> hook[i];
for (i = 1; i <= g; i++) cin >> w[i];
//initilize
memset(m, 0, sizeof(m));
for (k = 1; k <= c; k++)
m[1][hook[k] * w[1] + N]++;
//dp
for (i = 2; i <= g; i++)
{
for (j = 0; j < 2 * N; j++)
{
if (m[i - 1][j] == 0) continue;
for (k = 1; k <= c; k++)
m[i][j + hook[k] * w[i]] += m[i - 1][j];
}
}
cout << m[g][N] << endl;
return 0;
}
评论 (0)