rqnoj-202-奥运火炬登珠峰

本文主要是介绍rqnoj-202-奥运火炬登珠峰，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个二维背包问题。
注意两种物品可以带超过当前值。
那么就算出超过的部分的最小值。

若当前已经超过，那么最小值不可能出现在超过后在加一个值，所以当数值已经超过的时候，就不需要算超过的部分的超过了。

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define INF 999999999
using namespace std;
int dp[101][101];
int main()
{int t,a,n;int i,j,x,y,z;while(~scanf("%d%d",&t,&a)){for(i=0;i<101;i++){for(j=0;j<101;j++){dp[i][j]=INF;}}dp[0][0]=0;int fa,fb;fa=fb=0;scanf("%d",&n);while(n--){scanf("%d%d%d",&x,&y,&z);for(i=fa;i>=0;i--){for(j=fb;j>=0;j--){if(i+x<101&&j+y<101)dp[i+x][j+y]=min(dp[i][j]+z,dp[i+x][j+y]);}}if(fa+x<101)fa=fa+x;if(fb+y<101)fb=fb+y;}int MIN;MIN=INF;for(i=t;i<=fa;i++){for(j=a;j<=fb;j++){MIN=min(MIN,dp[i][j]);}}cout<<MIN<<endl;}return 0;
}

这篇关于rqnoj-202-奥运火炬登珠峰的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---