SDNU

SDNU-1044.花瓶插花

Description
有m朵花和n个花瓶，要把这些花全部插入某些花瓶中，花瓶和花都是有序的，花在花瓶中的先后顺序必须与给定顺序相同，每朵花插入每个花瓶能得到的美观程度都不一定相同，选择一些和花瓶，求插花能得到的最大美观程度。
Input
第一行是两个整数m, n(1 <= m <= n <= 1000)，表示花的数量和花瓶的数量。之后m行，每行n个正整数(<= 100)，这m行中第i行的第j个数字表示第i朵花插入第j个花瓶的美观程度。
Output
一个整数，最大的总美观程度。
Sample Input
3 5
5 9 3 2 4
1 3 2 9 5
4 2 1 3 5
Sample Output
23

又是一个dp题，一开始兴致冲冲的写出了状态方程，然后样例过了，缺WA了，最后搜了一下类似题的做法才知道是初始化的问题。（样例也是卡的这个点）
状态方程

dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+a[i][j]);//dp[i][j]表示前 i朵花放入前 j个瓶子 1

初始化的时候要注意了！

dp[0][0]=a[0][0]; for (int i=0;i<=n;i++)dp[0][i]=max(dp[0][i-1],a[0][i]);//对第一束花的初始化 for (int i=0;i<=m;i++)dp[i][i]=dp[i-1][i-1]+a[i][i];//对前 i朵花放入前 i个瓶子的初始化 12345

最后放上ac代码：

#include<cstdio> #include<iostream> using namespace std; int dp[1005][1005]; int a[1005][1050]; int main() {int m,n;cin>>m>>n;for (int i=0;i<m;i++) for (int j=0;j<n;j++) cin>>a[i][j];dp[0][0]=a[0][0];for (int i=1;i<=m;i++) dp[0][i]=max(dp[0][i-1],a[0][i]); for (int i=1;i<=n;i++) dp[i][i]=dp[i-1][i-1]+a[i][i];; for (int i=1;i<m;i++) for (int j=i+1;j<n;j++)//注意是i+1 dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+a[i][j]); cout<<dp[m-1][n-1]<<endl; return 0; }