潜水员【二维费用背包】

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int dp[22][80];//当前已有氧气量和氮气量 
int minn=1e9;
const int N = 1005;
int a[N],b[N],w[N];
int main()
{
    scanf("%d%d%d",&m,&n,&k);
    for(int i=1;i<=k;i++)
        scanf("%d%d%d",&a[i],&b[i],&w[i]);
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=m;j>=0;j--)
        {
            for(int p=n;p>=0;p--)//注意n->0 
            {
                int l1=j+a[i],l2=p+b[i];
                if(l1>m) l1=m;//当前>所需,直接截取下来就可以 
                if(l2>n) l2=n;
                dp[l1][l2]=min(dp[l1][l2],dp[j][p]+w[i]);
                /* 
                if(l1>=m&&l2>=n) 
                {
                    minn=min(minn,dp[l1][l2]);
                    //printf("%d\n",dp[l1][l2]);
                }
                */
            }
                
        }    
    }
    printf("%d",dp[m][n]);
    return 0;
}
/*
5 60 5
3 36 120 
10 25 129
5 50 250
1 45 130
4 20 119
*/

 

上一篇:HTML 在线编辑器


下一篇:E. Tree Shuffling(树上问题 + 贪心 )