ucas Alice's Food

题目：
问题描述
面对夜市上琳琅满目的美食, 吃货 Alice 正在犯难. 夜市上有 n 种食物. 每种都是不可分割地一份一份出售的. Alice 是一个珍惜食物的好孩子(吃货), 所以买到的食物她都会吃完不浪费. Alice 当然想尝试尽量多不同的的美味, 所以同一种食物她不会重复购买, 即最多只会买一份. 每份食物都有一个营养价值和美味指数. Alice当然想吃得又健康又美味, 所以她今晚的目标就是所吃食物的营养价值总和不能少于x, 而美味指数总和不能少于y. 精明的 Alice 当然想省下钱来明天再吃一顿, 所以她想花最少的钱实现她的目标.

所以 Alice 来求助同班的天才程序员 Bob, 就是你啦. 她告诉你 n 种食物的营养价值, 美味指数和价格, 以及她的目标 x 和 y. 你要告诉她最少要花多少钱才能达到目标.

输入
从标准文件输入, 第一行包括两个整数x和y, 由一个空格隔开(1<=x<=21,1<=y<=79)，表示 Alice 今晚的营养目标和美味目标。第二行包括一个整数n(1<=n<=1000)表示可选择的食物数量. 以下n行包括每种食物的描述：第i+2行包括三个整数xi、yi、pi,(1<=xi<=21,1<=yi<=79,1<=pi<=800)，分别为该种食物的营养价值, 美味指数和价格.

输出
你的程序应该输出一个整数，表示所选食物的最小总价格, 且其营养价值总和不小于x, 美味指数总和不小于y.

输入样例
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例
249
题解：01背包的变形，dp[i][j]代表营养价值为i，美味指数为j时的最小价格，因为必须满足营养价值与美味指数的要求，因此在状态转移时，dp[i][j]必须是有实际意义的值，因为x<=21 y<=79，因此dp数组的大小最多为dp[221][279],循环得到dp的值之后，选取最优的解即可。
代码：

#include<algorithm>
using namespace std;
int dp[55][205];
int xi[1010];
int yi[1010];
int pi[1010];
int main()
{
    int x,y;
    scanf("%d%d", &x, &y);
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d%d", &xi[i], &yi[i], &pi[i]);
    }
    for(int i = 0; i < 50; i++)
        for(int j = 0; j < 200; j++)
            dp[i][j] = 99999999;
    dp[0][0] = 0;
    for(int i = 0; i < n; i++){
        for(int x = 50; x - xi[i] >= 0; x--){
            for(int y = 200; y - yi[i] >= 0; y--){
                if(dp[x-xi[i]][y-yi[i]] != 99999999){
                    dp[x][y] = min(dp[x][y], dp[x-xi[i]][y-yi[i]] + pi[i]);
                }
            }
        }
    }
    int ans = 99999999;
    for(int i = x; i < 50; i++)
        for(int j = y; j < 200; j++)
            ans = min(ans, dp[i][j]);
    printf("%d\n", ans);
}