首页 > ACM题库 > HDU-杭电 > hdu 2291 Five in a Row, Again -动态规划-[解题报告]C++
2014
01-05

hdu 2291 Five in a Row, Again -动态规划-[解题报告]C++

Five in a Row, Again

问题描述 :

Each member of WHU ACM Team developed his/her own Five in a row AI application. They are planning to hold an AI competition on the online arena they just developed.
Each AI competitor has to compete with every other participator once. The winner of each game is awarded with credits while the loser gets nothing. No one gets credits in a tied game.

Every competitor has an experience point, which is crucial to the game. In each game, the competitor with higher experience point wins, except for tied games, in which two competitors have the same experience point.

Those AIs are so clever that they will learn from every game. That is to say, no matter win or lose, AIs’ experience point may increase after each game.

Alex, the team leader, has the privilege to arrange the game order. He wants to maximum his credit. Please help him solve the problem.

输入:

The input consists of several test cases. The first line of the input consists of an integer T, indicating the number of test cases.
Each test case starts with a line consist of an integer N, indicating the number of competitors. Each of the following N lines consists of N integers Eij, indicating the experience point the i-th competitor will increase after the game with the j-th competitor. Then, each of the following N lines consists of N integers Wij, indicating the credit the i-th competitor will gain if wins the game with the j-th competitor.

The last line of each test case consists of N integers Si, indicating the initial experience point of each competitor.

By the way, Alex is the first player.
Technical Specification

1. 1 ≤ T ≤ 11
2. 1 ≤ N ≤ 13
3. 0 ≤ Wij ≤ 10
4. 0 ≤ Eij, Si ≤ 1000

输出:

The input consists of several test cases. The first line of the input consists of an integer T, indicating the number of test cases.
Each test case starts with a line consist of an integer N, indicating the number of competitors. Each of the following N lines consists of N integers Eij, indicating the experience point the i-th competitor will increase after the game with the j-th competitor. Then, each of the following N lines consists of N integers Wij, indicating the credit the i-th competitor will gain if wins the game with the j-th competitor.

The last line of each test case consists of N integers Si, indicating the initial experience point of each competitor.

By the way, Alex is the first player.
Technical Specification

1. 1 ≤ T ≤ 11
2. 1 ≤ N ≤ 13
3. 0 ≤ Wij ≤ 10
4. 0 ≤ Eij, Si ≤ 1000

样例输入:

2
2
0 1
1 0
0 1
1 0
1 1
3
0 5 2
0 0 0
0 0 0
0 10 1
1 0 1
1 0 0
1 10 5

样例输出:

0
1

 hdu 2291 Five in a Row, Again

好几天了,这个题做完了一只没有总结,今天总结一下

原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2291

这个题我用的是状态压缩的dp,方法很笨,但是能ac,呵呵

先看看我查这个题解题报告时觉得不错的一个资料,其中给出了五种解法:

原文出自http://hi.baidu.com/spellbreaker/blog/item/5fd2f02ece315b301f308995.html

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int dp[1024 * 8][140];
int w[20][20];
int e[20][20];
int s[20];
int n;

int dfs(int fs,int x)
{
    if(dp[fs][x] != -1) return dp[fs][x];
    dp[fs][x] = 0;
    for(int i = 0;i < n-1;i++)
        if( (fs & (1 << i)) == 0)
        {
            int ss = (fs | (1 << i));
            if(x > s[i+1])
                dp[fs][x] = max(dp[fs][x],dfs(ss,x+w[0][i+1]) + e[0][i+1]);
            else dp[fs][x] = max(dp[fs][x],dfs(ss,x+w[0][i+1]));
        }
    return dp[fs][x];
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < n;j++)
                cin >> w[i][j];
        for(int i = 0;i < n;i++)
            for(int j = 0;j < n;j++)
                cin >> e[i][j];
        for(int i = 0;i < n;i++)
            cin >> s[i];
        memset(dp,-1,sizeof(dp));
        dfs(0,s[0]);
        int ma = 0;



        /*for(int i = 0;i < 150;i++)
        {
            cout << (1<<(n-1))-1 << " " << dp[(1<<(n-1))-1][i] << "\n";
            ma = max(ma,dp[0][i]);
        }*/

        cout << dp[0][s[0]] << "\n";
    }

    return 0;
}

解题转自:http://blog.csdn.net/wukonwukon/article/details/6720501


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。