rqnoj 202

題目描述

5月8日，在世界人民的共同關注下，象征着和平、友誼、聖潔的奧運火炬終于來到了世界之巅——珠穆朗瑪峰……

登上珠峰可不是所有人都能辦得了的，火炬手們為了登山要使用特殊的裝備。他有一個帶2種氣體的氣缸：一個為氧氣，一個為氮氣。讓火炬手需要各種的數量的氧和氮。火炬手有一定數量的氣缸。每個氣缸都有重量和氣體容量。火炬手為了完成傳遞需要特定數量的氧和氮。他完成傳遞所需氣缸的總重的最低限度的是多少？

例如：火炬手有5個氣缸。每行三個數字為：氧，氮的（升）量和氣缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果火炬手需要5升的氧和60升的氮則總重最小為249 （1，2或者4，5号氣缸）。

你的任務就是計算火炬手為了完成傳遞需要的氣缸的重量的最低值。

輸入格式

輸入：

第一行有2整數t，a（1<=t<=21，1<=a<=79）。它們表示氧，氮各自需要的量。

第二行為整數n （1<=n<=1000）表示氣缸的個數。

此後的n行，每行包括ti，ai，wi（1<=ti<=21，1<=ai<=79，1<=wi<=800）3整數。這些各自是：第i個氣缸裡的氧和氮的容量及汽缸重量。

輸出格式

輸出：

僅一行包含一個整數，為火炬手完成傳遞所需的氣缸的重量總和的最低值。

有一定思考難度的dp（對我這種蒟蒻來說是這樣的），因為不需要剛剛好裝滿，可以溢出，是以我在轉移的時候每次更新ans就行了。

dp[i,j,k]表示考慮了i個瓶子了，o2現有j,n2現有k的狀态，然後順推就行了。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <stack>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
int a,t,n;
int dp[][][];
int o2[],n2[],w[];
int main()
{
    scanf("%d%d",&a,&t);
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%d%d%d",&o2[i],&n2[i],&w[i]);
    }
    memset(dp,-,sizeof(dp));
    dp[][][]=;
    int ans=;
    for(int i=;i<n;i++)
    {
        for(int j=;j<=a;j++)
        {
            for(int k=;k<=t;k++)
            {
                if(dp[i][j][k]!=-)
                {
                    if(dp[i+][j][k]==-||dp[i+][j][k]>dp[i][j][k])
                    {
                        dp[i+][j][k]=dp[i][j][k];
                    }
                    if(dp[i+][j+o2[i+]][k+n2[i+]]==-||dp[i+][j+o2[i+]][k+n2[i+]]>dp[i][j][k]+w[i+])
                    {
                        dp[i+][j+o2[i+]][k+n2[i+]]=dp[i][j][k]+w[i+];
                    }
                    if(j>=a&&k>=t&&ans>dp[i+][j][k])
                    {
                        ans=dp[i+][j][k];
                    }
                    if(j+o2[i+]>=a&&k+n2[i+]>=t&&ans>dp[i+][j+o2[i+]][k+n2[i+]])
                    {
                        ans=dp[i+][j+o2[i+]][k+n2[i+]];
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
}