POJ1157

POJ1157

题目大意：有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;
}