题目链接:
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;
}
}