题目链接:

http://poj.org/problem?id=1837
题意:有个天平每边有N个刻度,负数代表在左边,整数代表在右边,然后有M个砝码。问挂完这M个砝码使天平平衡的有多少种方案?

竟然是个dp,感觉这个转换很牛皮呀,dp[i][j]表示前i个物品挂完天平状态是j的方案数,感觉只要把这个状态构建好了转移方程其实还是挺简单的

遇到的问题

我在做的时候遇到了两个问题:

①用map

因为第二维是天平的状态有负数,而我又不想加偏置,所以用了个map来弄dp
以前都阔以的啊,今天居然超时了,怎么算复杂度也够呀,map在我心中一直是log级的存在,结果。。。好像他的复杂度是个玄学,里面是那种高级的红黑树平衡树那些,反正就是要看情况
以后要注意了,比赛的时候T一波才亏

②初始化

我不是用map超时嘛,我就想节约一次,就把dp[1][j]想直接初始化了,结果我写成什么了

	dp[0][0+zhong]=1;
	for(int i=1;i<=M;i++)
	{
		for(int j=1;j<=N;j++)dp[1][a[i]*b[j]+zhong]=1;
	}

很明显地没有理解深入,为什么遍历a[i],明明前1个物品就只有a[1]一个物品,我却把所有物品都拿来弄了一次
所以应该是这样

	dp[0][0+zhong]=1;
	for(int j=1;j<=N;j++)dp[1][a[1]*b[j]+zhong]=1;

感谢卿老板T_T

//#include"bits/stdc++.h"
#include"iostream"
#include"map"
#include"time.h"
#include"cstring"
#include"cmath"
using namespace std;
typedef long long LL;
const int maxn=100+5;
const int MOD=1e9+7;
//map<int,int>dp[maxn];//dp[i][j]表示挂第i个砝码后平衡状态是j,因为平衡状态有负数,我又不想移动所以用了map
LL dp[maxn][20000];
const int zhong=1e4;//偏置 
int a[maxn],b[maxn];//砝码重量,挂钩位置
clock_t t1,t2;
int main()
{
	int N,M;
	while(cin>>N>>M)
	{
		memset(dp,0,sizeof dp);
		for(int i=1; i<=N; i++)cin>>b[i];
		for(int i=1; i<=M; i++)cin>>a[i];
		dp[0][0+zhong]=1;
		for(int j=1;j<=N;j++)dp[1][a[1]*b[j]+zhong]=1;
		for(int i=2; i<=M; i++)
		{
			for(int j=-6500; j<=6500; j++)
			{
				for(int k=1; k<=N; k++)dp[i][j+zhong]+=dp[i-1][j-a[i]*b[k]+zhong];
			}
		}
		cout<<dp[M][0+zhong]<<endl;
	}
}