题目大意:有f朵花要插到v个花瓶里面去。。。不同的花插到不同的花瓶有不同的美观程度,求最大的美观程度,,还有一个限制条件,如i>j,则编号为i的花能插的花瓶编号也必须大于 编号为j的花所插花瓶的编号。(因为没有注意到这个条件,我想了n久~)。
好的我们说思路
理解题意后还是比较好写的,这里又有花又有花瓶的,肯定是用二维dp啦。假设dp[i][j],为第i朵花插到第j个瓶子中能获得的最大美观程度,dp[i][j]=max(dp[i-1][k]+a[i][j]),k>=i-1&& k<j ,a[i][j]为给出的每朵花对应花瓶的美观程度.
#include "iostream" using namespace std; #define len 110 int main() { int f,v; int i,j,k; int a[len][len]; int dp[len][len];//dp[i][j] 表示第i朵花插到第j个瓶子的最大价值 dp[i][j]=max(dp[i-1][k]+a[i][k]); scanf("%d",&f); scanf("%d",&v); for (i=0;i<f;i++) { memset(dp[i],0,sizeof(dp[i])); for (j=0;j<v;j++) { scanf("%d",&a[i][j]); if (i==0) { dp[i][j]=a[i][j]; } } } for (i=1;i<f;i++) { for (j=i;j<v;j++) { int max=-999999; for (k=i-1;k<j;k++) { if (max<dp[i-1][k]+a[i][j]) { max=dp[i-1][k]+a[i][j]; } } dp[i][j]=max; } } int maxt=dp[f-1][0]; for (i=0;i<v;i++) { if(maxt<dp[f-1][i]) maxt=dp[f-1][i]; } cout<<maxt<<endl; return 0; }
相关推荐
北大POJ初级-动态规划 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
POJ3211--Washing Clothes
北大POJ3414-Pots 解题报告+AC代码
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ1159-Palindrome 解题报告+AC代码
poj 1000-3000部分代码 网上收集
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大POJ1159-Palindrome