洛谷题解 P1441 【砝码称重】

题目链接

DP是不可能DP的,这辈子不可能DP的,只有打打模拟队列才能维持的了生活的样子,DP超难调的,一点都不好玩(还是要学的23333

在经历了二维dp调不好,一维dp看不懂,bitset啥玩意的懵⚪之后,我决定尝试一下模拟这个过程。。。

感谢@WLZS 提供的深搜剪枝思路,出现了60->AC的奇迹。

说一说思路吧,

  1. 深搜全排列去掉砝码(记得剪枝变成组合否则60分TLE)
  2. 砝码称重过程:
    1. 找到一个没有去掉的砝码,加入队列
    2. 拿一个砝码,和已经加入队列的重量相加,最后自己加入队列(想一想为什么不先加入队列)
    3. 重复上一步,加完后更新答案的值

以下为代码部分

代码中变量说明

/*全局变量*/
int w[25];  	//砝码重量
int vis[25]; 	//dfs标记该砝码是否已经取走
int all; //所有砝码重量,用于剪枝
/*int dfs(int step,int now,int b)*/
int step;	//搜索到哪一步 
int now; 	//剩下的质量
int b;    	//标记从哪个坐标开始搜索
int last;  	//标记上次搜索的坐标,用于剪枝
/*void check()*/
int book[2005]; 	//标记重量是否出现过
int mark[25];		//标记该砝码是否可用
int que[2005];   	//加法队列

———————————————– AC代码 ? ———————————————–

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, w[25], vis[25], ans, all;
void dfs(int step, int now, int b);
void check()
{
    int book[2005] = {0};
    int que[2005] = {0};
    int mark[25] = {0};
    int tans = 0;
    for (int i = 1; i <= n; i++)
        if (vis[i])
            mark[i] = 1;  //我们用一个mark数组来判定当前情况下可用的砝码
    int tail, start;
    tail = 1;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            start = i;  //start为第一个可以加入队列的砝码下标
            break;
        }
    }
    mark[start] = 1;
    que[tail] = w[start];
    book[w[start]] = 1;
    tail++;  //队列初始化操作 ?
    tans++;
    for (int i = start + 1; i <= n; i++)
    {
        if (!mark[i])
        {
            mark[i] = 1;
            int temp = tail - 1; //temp为当前队列长度值
            for (int j = 1; j <= temp; j++)
            {
                int t = w[i] + que[j];
                if (!book[t])  //如果该值没有出现就加入队列并且 tans++
                {
                    book[t] = 1;
                    que[tail] = t;
                    tail++;
                    tans++;
                }
            }
            if (!book[w[i]]) //结束后把自己加入队列
            {
                book[w[i]] = 1;
                que[tail] = w[i];
                tail++;
                tans++;
            }
        }
    }
    ans = max(ans, tans);
}
void dfs(int step, int now, int b)
{
    if (now <= ans) //如果当前值小于答案值,剪枝(好像作用不大)
        return;
    if (step == m + 1)
    {
        check();
        return;
    }
    int last = 0;
    for (int i = b; i <= n; i++)
    {
        if (!vis[i] && w[i] != w[last]) //作用很大的一个剪枝,可以防止出现两个相同的序列
        {
            vis[i] = 1;
            dfs(step + 1, now - w[i], i + 1);
            vis[i] = 0;
            last = i;
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i], all += w[i];
    sort(w + 1, w + n + 1); //排序保证深搜的单调性
    dfs(1, all, 1);
    cout << ans;
    return 0;
}

通过我对洛谷IDE的测试,发现同样的代码,c++11比其他的快很多,不知道CCF评测机是怎样。。

以上