房门户网站如何做优化/厦门关键词优化报价

　　

　　　　1、如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马。

　　　　2、如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马。

　　　　3、如果田忌剩下的马中最强的马和齐王剩下的最强的马打平的话，可以选择打平或者用最差的马输掉比赛。

 　　　

　　　　设  表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从“头”取了j匹较强的马，从“尾”取了i-j匹较弱的马，所能够得到的最大盈利。 　　　

　　　　状态转移方程如下：

　　　　　　　　

　　　　注意边界条件的判定 

// Code by yefeng1627
// Time 2013-1-17
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;const int N = 1010;
const int inf = 0x3fffffff;
int A[N],B[N], n;
int dp[N][N], G[N][N];int cmp(int a,int b)
{    return a > b;    }
int main()
{while( scanf("%d", &n) , n ){for(int i = 1; i <= n; i++)scanf("%d", &A[i]);for(int i = 1; i <= n; i++)scanf("%d", &B[i]);sort( A+1, A+n+1, cmp);sort( B+1, B+n+1, cmp);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){if( A[i] > B[j] ) G[i][j] = 200;else if( A[i] == B[j] ) G[i][j] = 0;else    G[i][j] = -200;}for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)dp[i][j] = -inf;dp[0][0] = 0;int ans = -inf;for(int i = 1; i <= n; i++)for(int j = 0; j <= i; j++){if( i-1 >= j ) dp[i][j] = max( dp[i][j], dp[i-1][j]+ G[ n+1-(i-j) ][i] );if( j > 0 )    dp[i][j] = max( dp[i][j], dp[i-1][j-1] + G[j][i] );}for(int i = 0; i <= n; i++)ans = max( ans, dp[n][i] );printf("%d\n", ans );    }return 0;
}