状压DP

HDU 1074 Doing Homework

Posted on

虽然可以算得上是道水题,但作为我第一道状压DP,还是把它写入我的博客。
觉得这道题作为入门题是极好的,比网上说的什么矩阵的好理解的多!!
因为几乎只涉及了状压

特别想感慨一句,dp真的是个优美的暴力啊……

题意:
有几门课的作业,分别给出截止时间,完成所需时间,没拖一天扣一分,问最少扣多少分,并输出写作业顺序。

思路:
总的思路是对于每一个状态,都进行课程的枚举,并计算花费时间,拖作业时间,从而进行状态转移,每次状态转移都使拖作业的时间最小即可。
不是暴力??但是真的很优美!
课程数很小,只有15门,因此状压无压力。

AC Code

#include <cstdio>
#include <cstring>
#include <numeric>
#include <queue>
#include <stack>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

const int max_n = 16;
const int max_m = 110;

int n;
bool vis[1<<max_n];

struct co {
    int deadline, cost;
    char name[max_m];
} course[max_n];

struct p {
    int cost, bey, pre;
} dp[1 << max_n];

void output(int state)
{
    if (!state)
        return;
    output(dp[state].pre);
    int idx = state ^ dp[state].pre, pos = 0;
    while ((idx & 1) == 0)
        idx >>= 1, pos++;
    puts(course[pos].name);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        fill(vis, false);
        each(i, n) scanf("%s %d %d", course[i].name, &course[i].deadline, &course[i].cost);
        int en = (1 << n);
        each(i, en) each(j, n)
        {
            int j2 = (1 << j);
            if (!(i & j2)) {
                int cur = i | j2;
                dp[cur].cost = dp[i].cost + course[j].cost;
                int bey = (dp[cur].cost > course[j].deadline ? dp[cur].cost - course[j].deadline : 0) + dp[i].bey;
                if (!vis[cur] || bey < dp[cur].bey)
                    vis[cur] = true, dp[cur].bey = bey, dp[cur].pre = i;
            }
        }
        printf("%d\n", dp[en - 1].bey);
        output(en - 1);
    }
    return 0;
}
哈夫曼树

CodeForces 226 B Naughty Stone Piles

Posted on

遇到的第二道哈夫曼树,这个哈夫曼树有些特别,当你将两个结点组合的时候,你只需要付出权值较小的花费。
简单说,结点权值组合的时候并不会产生新的结点!!
这就可以完全摒弃优先队列,直接用数组实现以求更为高效。

上次意外地发现两个队友都不会哈夫曼树……真是惊了……

题意:
有几堆石头,要你将他们堆成一堆。两堆石头堆成一堆的花费是石头堆较小的石头数量。q个询问,每次询问限制一堆石头,被其他石头合并的次数。

思路:
这道题,若是转化成图来说就是一个k叉哈夫曼树,然而不会产生新结点,也就是说所有结点的权值和位置都已经可以直接求得了。
将他降序排序,每次将同一层的权值乘以他的深度就是该层的花费。

: 下表很容易爆 int 自己想想很容易想到……
然而RE了好几发……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 5;
int n;
ll ans[maxn], sum[maxn], ary[maxn];

void solve(int q)
{
    ll dep = 1, idx = 1, nxt;
    ll tmp, res = 0, d = q;
    while (idx <= n) {
        nxt = idx + d <= n ? idx + d : n;
        tmp = sum[nxt] - sum[idx];
        res += tmp * dep;
        idx += d, dep++, d *= q;
    }
    printf("%lld ", ans[q] = res);
}

int main()
{
    int qn, q;
    scanf("%d", &n);
    range(i, 1, n) scanf("%lld", ary + i);
    sort(ary + 1, ary + 1 + n, greater<int>());
    range(i, 1, n) sum[i] = ary[i] + sum[i - 1];
    scanf("%d", &qn);
    while (qn--) {
        scanf("%d", &q);
        if (ans[q])
            printf("%lld ", ans[q]);
        else
            solve(q);
    }
    return 0;
}
尺取

CodeForces 367 B Sereja ans Anagrams

Posted on

这是我在比赛中写的第一道尺取,这也算是一道很明显的尺取题,但是看了其他人的题解都说司马stl……
实际上代码还是我短很多……

但是第一次的尺取搞得我WA了7发,其中忘记排序4发……
总的来说还是不熟练吧……

题意:
给你两个序列分别为n,m个,和位置差,要你求出有多少个起始位置,使得从这位置开始后连续的m个元素与第二个序列相同。不要求顺序。

思路:
尺取,用一个map记录第二个序列各个元素的序列,再用一个map在尺取途中记录元素个数,只要小于原map的元素个数就可以继续往后取,最终结果必然是取得数目与m相同,每次取完判断一下即可。

AC Code

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn = 2e5+5;

map<int,int> ma;
map<int,int> mb;
int ary[maxn];
int kao[maxn];

int main()
{
    int n,m,p,a,b;
    scanf("%d %d %d",&n,&m,&p);
    for(int i=1;i<=n;i++)
        scanf("%d",ary+i);
    for(int i=0;i<m;i++) {
        scanf("%d",&a);
        mb[a]++;
    }
    int ans =0;
    for(int i=1;i<=p;i++) {
        int a=i,b=i;
        ma.clear();
        while(a<=n)
        {
            if(b<a)
                b=a;
            while(b<=n && ma[ary[b]]<mb[ary[b]]) {
                ma[ary[b]]++;
                b+=p;
            }
            if((b-a)/p==m)
                kao[ans++]=a;
            if(ma[ary[a]]>0)
                ma[ary[a]]--;
            a+=p;
        }
    }
    printf("%d\n",ans);
    sort(kao,kao+ans);
    for(int i=0;i<ans;i++)
        printf("%d ",kao[i]);
    return 0;
}
简单DP

HDU 5074 Hatsune Miku

Posted on

老实说有点崩溃,一场训练赛,3道dp都没出,两道还是全世界都A了
毫无疑问,又落后一截……
实在不明白他们的dp为什么这么6……

题意:
给你一个序列 \( a_1 a_2 a_3 a_4 …… a_n \)
要你求相邻两个元素在矩阵中的数值和。
矩阵已给定,但是如果序列元素为负数,则可以为任意元素。

思路:
渐渐觉得dp就是暴力……
四种情况

ary[i-1] < 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i - 1][k] + mat[k][j])
ary[i-1] < 0 && ary[i] > 0dp[i][ary[i]] = max(dp[i][ary[i]], dp[i - 1][j] + mat[j][ary[i]])
ary[i-1] > 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][j])
ary[i-1] > 0 && ary[i] > 0dp[i][ary[i]] = dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][ary[i]]

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 110;

int mat[maxn][maxn], dp[maxn][maxn];
int ary[maxn];

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, m) range(j, 1, m) scanf("%d", &mat[i][j]);
        range(i, 1, n) scanf("%d", ary + i);
        fill(dp, 0);
        range(i, 2, n)
        {
            if (ary[i - 1] < 0)
                if (ary[i] < 0)
                    range(j, 1, m) range(k, 1, m) dp[i][j] = max(dp[i][j], dp[i - 1][k] + mat[k][j]);
                else
                    range(j, 1, m) dp[i][ary[i]] = max(dp[i][ary[i]], dp[i - 1][j] + mat[j][ary[i]]);
            else if (ary[i] < 0)
                range(j, 1, m) dp[i][j] = max(dp[i][j], dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][j]);
            else
                dp[i][ary[i]] = dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][ary[i]];
        }
        int ans = 0;
        range(i, 1, m) ans = max(ans, dp[n][i]);
        printf("%d\n", ans);
    }
    return 0;
}