小x买年货_纪中1701_dp

题目描述

春节将至，小x要去超市购置年货，于是小x去了自己经常去的都尚超市。刚到超市，小x就发现超市门口聚集一堆人。用白云女士的话说就是：“那家伙，那场面，真是人山人海，锣鼓喧天，鞭炮齐呤，红旗招展。那可真是相当的壮观啊！”。好奇的小x走过去，奋力挤过人群，发现超市门口贴了一张通知，内容如下：

值此新春佳节来临之际，为了回馈广大顾客的支持和厚爱，特举行春节大酬宾、优惠大放送活动。凡是都尚会员都可用会员积分兑换商品，凡是都尚会员都可免费拿 k 件商品，

blablabla….

还没看完通知，小x就高兴的要死，因为他就是都尚的会员啊。迫不及待的小x在超市逛了一圈发现超市里有 n 件他想要的商品。小x顺便对这 n 件商品打了分，表示商品的实际价值。小x发现身上带了 v1 的人民币，会员卡里面有 v2 的积分。他想知道他最多能买多大价值的商品。

由于小x想要的商品实在太多了，他算了半天头都疼了也没算出来，所以请你这位聪明的程序员来帮帮他吧。

输入

第一行是四个整数 n，v1，v2，k；

然后是 n 行，每行三个整数 a，b，val，分别表示每个商品的价钱，兑换所需积分，实际价值。

其中，1 <= n <= 100，0 <= v1, v2 <= 100，0 <= k <= 5，0 <= a, b, val <= 100。

Ps. 只要钱或者积分满足购买一件商品的要求，那么就可以买下这件商品。

输出

输出能买的最大价值。

数据范围限制

1 <= n <= 100，0 <= v1, v2 <= 100，0 <= k <= 5，0 <= a, b, val <= 100。

Analysis

一眼题，这不就是多几维的背包嘛

f[i][j][k][l] 表示前i项花j钱k积分l次免费机会拿的最大价值

转移自己想(滑稽脸

然后i是可以滚的，这次用了一个高级的方法

太水了太水了

Code

#include <stdio.h>
#include <string.h>
#define rep(i, a, b) for (int i = a; i <= b; i += 1)
#define fill(x, t) memset(x, t, sizeof(x))
#define N 6
using namespace std;
struct pos{
    int x, y;
    inline pos operator +(pos b){
        pos a = *this;
        return (pos){b.x + a.x, b.y + a.y};
    }
    inline bool check(int n, int m){
        pos a = *this;
        return (a.x >  && a.x <=n && a.y >  && a.y <= m);
    }
}dir[] = {{-, }, {, }, {, -}, {, }};
int map[N + ][N + ];
bool flag[N * N * N * N];
pos q[N * N * N * N], d[N * N * N * N];
int spilt(pos st, int n, int m){
    fill(flag, false);
    int cnt = ;
    rep(k, , ){
        q[++cnt] = st;
        d[cnt] = dir[k];
    }
    map[st.x][st.y] = ;
    int tot = cnt;
    while (tot > ){
        rep(i, , cnt){
            if (!flag[i]){
                q[i] = q[i] + d[i];
                if (!q[i].check(n, m)){
                    q[i] = d[i] = (pos){, };
                    tot -= ;
                    flag[i] = true;
                }
            }
        }
        rep(i, , cnt){
            if (!flag[i]){
                if (map[q[i].x][q[i].y]){
                    map[q[i].x][q[i].y] += ;
                    flag[i] = true;
                    d[i] = (pos){, };
                    tot -= ;
                }
            }
        }
        rep(i, , cnt){
            if (map[q[i].x][q[i].y] > ){
                q[i] = d[i] = (pos){, };
                flag[i] = true;
            }
        }
        int tmp = cnt;
        rep(i, , n){
            rep(j, , m){
                if (map[i][j] > ){
                    map[i][j] = ;
                    rep(k, , ){
                        q[++tmp] = (pos){i, j};
                        d[tmp] = dir[k];
                        tot += ;
                    }
                }
            }
        }
        cnt = tmp;
    }
}
int add(pos now, int n, int m){
    map[now.x][now.y] += ;
    if (map[now.x][now.y] > ){
        spilt(now, n, m);
    }
}
int main(void){
    freopen("drops.in", "r", stdin);
    freopen("drops.out", "w", stdout);
    int n = N, m = N;
    while (~scanf("%d", &map[][])){
        rep(i, , n){
            scanf("%d", &map[][i]);
        }
        rep(i, , n){
            rep(j, , m){
                scanf("%d", &map[i][j]);
            }
        }
        int opt;
        scanf("%d", &opt);
        rep(i, , opt){
            int x, y;
            scanf("%d%d", &x, &y);
            add((pos){x, y}, n, m);
        }
        rep(i, , n){
            rep(j, , m){
                printf("%d ", map[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return ;
}