小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 ;
}