3417. 砝码称重

https://www.acwing.com/problem/content/3420/

一眼dp,但是还是先走个暴搜看看,开始的时候我这样想,由于天平两边都可以称,需要减的操作,数组无法存储负数下标,于是我这里加了个偏移量100000,于是只过了一半的数据233(但是实际上小于0的下标不需要计算,因为砝码嘛,也需要联系实际,小于0的重量物品怎么可能称嘛!)

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
const int M = 1e5+1000;
int a[N];
int n;
int st[M];
int cnt;
void dfs(int step,int sum)
{
    if(step==n+1)
    {
        st[sum+100000]++;
        return;
    }
    dfs(step+1,sum);
    dfs(step+1,sum+a[step]);
    dfs(step+1,sum-a[step]);
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs(0,0);
    for(int i=100001;i<M;i++)if(st[i])cnt++;
    cout << cnt << endl;
    
    return 0;
}

这样想过后,稍作修改,可以优化成这样:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
const int M = 1e5+10;
int a[N];
int n,cnt;
bool st[M];
void dfs(int step,int sum)
{
    if(step==n+1)
    {
        if(sum>0 && !st[sum])
        {
            cnt++;
            st[sum]=true;
        }
        return;
    }
    dfs(step+1,sum);
    dfs(step+1,sum+a[step]);
    dfs(step+1,sum-a[step]);
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs(0,0);
    cout << cnt << endl;
    return 0;
}

 但是怎么改变不了超时的命运,所以再进一步优化成记搜

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
const int M = 200010;
int a[N];
int n,cnt;
bool st[N][M];
bool f[M];
void dfs(int step,int sum)
{
    if(st[step][sum])return;
    st[step][sum]=1;
    f[sum]=1;//标记答案
    if(step==n+1)return;
    dfs(step+1,sum);
    dfs(step+1,sum+a[step]);
    dfs(step+1,sum-a[step]);
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs(0,0);
    for(int i=1;i<=M;i++)if(f[i])cnt++;
    cout << cnt << endl;
    return 0;
}

如此可以过了,但本题实际上考察的是dp233
再次尝试dp做法
首先,对于整个DP,状态表示:用f[i][j]表示,(i,j)表示从前i个砝码中选,且总重量为j的所有方案的集合,其属性(即f[i][j]本身的值)是是否为空(即j是否可以被已经选的砝码所表示),为布尔值
状态计算:对于最后一步操作:我们可以分成三份(大问题分解为小问题):1.不选最后一个砝码 2.选最后一个砝码,且放在正的方向上 3.选最后一个砝码,将其放在负的方向上
对于第一步操作:我们可以用f[i-1][j]来表示这步操作
对于第二步操作: 由于1~(i-1)之间的砝码我们未确定,但是第i个砝码(最后一个)我们是确定要选的,且放在正的方向上,也就是说,加上这最后一个砝码可以称取的重量大小为j ,用可解得子问题推出大问题,我们可以用f[i-1][j-w[i]]来表示这步操作
对于第三步操作:同第二步一样,由于1~(i-1)之前未确定,但是最后一个确定了,可以用f[i-1][j+w[i]]来表示这步操作

那么只要这三种子问题,有一种非空,即可以被表示出来,那么f[i][j]就可以被表示出来,就非空

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110,M = 200010;
int a[N];
bool f[N][M];
int n,cnt,sum;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=sum;j++)
        {
            f[i][j]=f[i-1][j]|f[i-1][abs(j-a[i])]|f[i-1][j+a[i]];//镜像操作
        }
    for(int j=1;j<=sum;j++)
    {
        if(f[n][j])cnt++;
    }
    cout << cnt << endl;
    return 0;
}