題目很有意思。
女生找男朋友的問題。
以天津大學為背景，表現出男生比女生多的這個問題。
解決方法就是一個簡單的dp問題了。
data[i][j]表示還剩下i個女生j個男生。
狀態轉移方程
data[i][j]=max{data[i][j-1],data[i-1][j-1]+map[i][j]};
1
#include<stdio.h>
2//#define int long long
3int data[600][600];
4int map[600][600];
5#define oo -2000000001
6void di(int i,int j)
7
{
8
int max;
9 if(i==0)
10
{
11 data[i][j]=0;
12 return;
13
}
14 if(i>j)
15 {
16 data[i][j]=oo-1;
17 return;
18 }
19 max=oo-1;
20 if(i-1>=0 && j-1>=0)
21 {
22 if(data[i-1][j-1]==oo)di(i-1,j-1);
23 if(data[i-1][j-1]+map[i][j]>max)
24 max=data[i-1][j-1]+map[i][j];
25 }
26 if(j-1>=0)
27 {
28 if(data[i][j-1]==oo)di(i,j-1);
29 if(data[i][j-1]>max)
30 max=data[i][j-1];
31 }
32 data[i][j]=max;
33 return;
34
35
}
36int main()
37{
38 int i,j,n,m;
39 while(scanf("%d%d",&n,&m))
40 {
41 if(n==0 && m==0)break;
42 for(i=1;i<=n;i++)
43 for(j=1;j<=m;j++)scanf("%d",&map[i][j]);
44 for(i=0;i<=n;i++)
45 for(j=0;j<=m;j++)data[i][j]=oo;
46 di(n,m);
47 printf("%d\n",data[n][m]);
48 }
49 return 0;
50}
51