[c]sdnuoj1044 花瓶插花

[c]sdnuoj1044 花瓶插花

210.44.14.31/problem/show/1044

题目标题：花瓶插花

题目内容：有m朵花和n个花瓶，要把这些花全部插入某些花瓶中，花瓶和花都是有序的，花在花瓶中的先后顺序必须与给定顺序相同，每朵花插入每个花瓶能得到的美观程度都不一定相同，选择一些和花瓶，求插花能得到的最大美观程度。

这个题是一个dp，状态转移方程为re[i][j]=max(re[i-1][j-1]+a[i][j],re[i][j-1]);

#include<iostream>
#include<stdio.h>
using namespace std;int a[1010][1010];
int re[1010][1010]={0};int max(int a,int b){if(a<b) a=b;return a;
}int main()
{int m,n;cin>>m>>n;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){re[i][j]=max(re[i-1][j-1]+a[i][j],re[i][j-1]);}}cout<<re[m][n];return 0;
}