POJ 1157 花瓶插花问题

POJ 1157 花瓶插花问题

大意为F束花插入V个瓶子里面，花要按编号插，不同花插入不同的花瓶有不同的美观程度，要求最大的美观程度。 采用DP做法。 此题有两种解题，两种不同状态函数的表示。一种f[i][j]表示第i束花插入第[j]个瓶子里面所获得的最大的美观程度。则状态转移函数可以表示为f[i][j]=max(f[i-1][k]+a[i][j])其中i-1<=k<j; 则输出为f[F][F]-f[F][V]之间的最大值。
解法一代码:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, m;
const int maxn = 104;
int fv[maxn][maxn];
int dp[maxn][maxn];
void solve()
{int i, k , j, q;for(i=1;i<n;i++){for(k=i;k<m;k++){                        //第i束花插入第k个瓶子里面dp[i][k]=-10000;for(j=i-1;j<k;j++){              //取其中的最大值q=dp[i-1][j]+fv[i][k];if(q>dp[i][k])dp[i][k]=q;}}}
}
int main()
{cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> fv[i][j];}}for (int i = 0; i < m; ++i) {dp[0][i] = fv[0][i];}solve();int ans = dp[n-1][n-1];for(int i = n - 1; i < m; i++)if(ans < dp[n-1][i])ans = dp[n-1][i];                     //为其中的最大值printf("%dn",ans);return 0;
}

第二种解法的状态函数为f[i][j]表示第i束花插入前j个瓶子里面。则状态转移函数为f[i][j]=max(f[i-1][j-1]+a[i][j],f[i][j-1]) 因为有两种插法，一：第i束花插入第j个瓶子里面，则为f[i][j]=f[i-1][j-1]+a[i][j].二：第i束花不插入第j个瓶子里面，则f[i][j]=f[i][j-1]。两者当中取极大 解法二代码:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, m;
const int maxn = 104;
int fv[maxn][maxn];
int dp[maxn][maxn];
void solve()
{for (int i = 1; i < n; ++i) {for (int j = i + 1; j < m; ++j) {dp[i][j] += max(dp[i][j - 1], dp[i - 1][j - 1] + fv[i][j]);}}
}
int main()
{cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> fv[i][j];}}dp[0][0] = fv[0][0];for (int i = 1; i < m; ++i) {dp[0][i] = max(dp[0][i - 1], fv[0][i]);}for(int i=1; i<n; i++)dp[i][i]=dp[i-1][i-1] + fv[i][i];solve();cout << dp[n - 1][m - 1] << endl;                     //为其中的最大值return 0;
}