跳至正文

USACO 3.3.3. Shopping Offers 商店购物

  一道DP题,DP的方程很简单:
  f[a][b][c][d][e] = min(f[a][b][c][d][e], f[a – cost[0][0]][b – cost[0][1]][c – cost[0][2]][d – cost[0][3]][e – cost[0][4]], f[a – cost[1][0]][b – cost[1][1]][c – cost[1][2]][d – cost[1][3]][e – cost[1][4]]…);
  代码如下:
/
LANG: C
ID: zqynux2
PROG: shopping
/
#include <stdio.h>
#define min(a, b) ((a)<(b)?(a):(b))
struct you{
        int len;
        struct thing{
                int id, num;
        }buy[5];
        int priece;
}buy[99];
int money[6];
int num[6];
int good[1000];
int f[6][6][6][6][6];
int n, m;

int s[6];

void init(int now)
{
        int i;
        if(now == m){
                for(i = 0; i < m; i++){
                        f[s[0]][s[1]][s[2]][s[3]][s[4]] += money[i + 1] s[i];
                }
                return;
        }
        for(i = 0; i <= 5; i++){
                s[now] = i;
                init(now + 1);
        }
}

void deal(int now)
{
        int used[6];
        int i;
        memset(used, 0sizeof(used));
        for(i = 0; i < buy[now].len; i++){
                used[good[buy[now].buy[i].id]] += buy[now].buy[i].num;
        }
        if(used[0] != 0){
                return;
        }
        for(i = 0; i < 5; i++){
                if(used[i + 1] > s[i]){
                        return;
                }
        }
        f[s[0]][s[1]][s[2]][s[3]][s[4]] = min(f[s[0]][s[1]][s[2]][s[3]][s[4]], 
                f[s[0] – used[1]][s[1] – used[2]][s[2] – used[3]][s[3] – used[4]][s[4] – used[5]]
                + buy[now].priece);
}

void srch(int now)
{
        int i;
        if(now == m){
                for(i = 0; i < n; i++){
                        deal(i);
                }
                return;
        }
        for(i = 0; i <= 5; i++){
                s[now] = i;
                srch(now + 1);
                //写成了init 
        }
}

int main(void)
{
        int i, j;
        freopen("shopping.in""r"stdin);
        freopen("shopping.out""w"stdout);
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &buy[i].len);
                for(j = 0; j < buy[i].len; j++){
                        scanf("%d%d", &buy[i].buy[j].id,
                                        &buy[i].buy[j].num);
                }
                scanf("%d", &buy[i].priece);
        }
        scanf("%d", &m);
        for(i = 1; i <= m; i++){
                scanf("%d%d%d", &j, &num[i], &money[i]);
                good[j] = i;
        }

        init(0);                       / 将价格进行初始化 /
        srch(0);                       /
 DP */

        printf("%d\n", f[num[1]][num[2]][num[3]][num[4]][num[5]]);
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。