3月 | 2017 | 超客的水墨烟雨

poj2181

maksyuki 发表于 oj 分类，标签: DP-线性DP

04 3月 2017

Jumping Cows

Farmer John's cows would like to jump over the moon, just like the cows in their favorite nursery rhyme. Unfortunately, cows can not jump. The local witch doctor has mixed up P (1 <= P <= 150,000) potions to aid the cows in their quest to jump. These potions must be administered exactly in the order they were created, though some may be skipped.

Each potion has a 'strength' (1 <= strength <= 500) that enhances the cows' jumping ability. Taking a potion during an odd time step increases the cows' jump; taking a potion during an even time step decreases the jump. Before taking any potions the cows' jumping ability is, of course, 0.

No potion can be taken twice, and once the cow has begun taking potions, one potion must be taken during each time step, starting at time 1. One or more potions may be skipped in each turn.

Determine which potions to take to get the highest jump.

Input

* Line 1: A single integer, P

* Lines 2..P+1: Each line contains a single integer that is the strength of a potion. Line 2 gives the strength of the first potion; line 3 gives the strength of the second potion; and so on.

Output

* Line 1: A single integer that is the maximum possible jump.

Sample Input

Sample Output

Source

USACO 2003 U S Open Orange

题目类型：线性DP

算法分析：dp[0][i]表示前i个数经过偶数次跳跃增加的最大能量值，dp[1][i]表示前i个数经过奇数次跳跃增加的最大能量值，初始化dp[0][0] = 0，状态转移方程为dp[0][i] = max(dp[0][i-1], dp[1][i-1] - a[i])，dp[1][i] = max(dp[1][i-1], dp[0][i-1] + a[i])，最后输出dp[0][P]和dp[1][P]的最大值即可

/**************************************************
filename       :f.cpp
author         :maksyuki
created time   :2017/3/4 10:34:52
last modified  :2017/3/4 11:02:52
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CPPFF ifstream cin ("in")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 66666;

int a[maxn], dp[2][maxn];

int main()
{
    //CFF;
    //CPPFF;
    int P;
    scanf("%d", &P);
    for(int i = 1; i <= P; i++)
        scanf("%d", &a[i]);
    
    for(int i = 0; i < maxn; i++)
        dp[0][i] = dp[1][i] = -INF;

    dp[0][0] = 0;
    for(int i = 1; i <= P; i++)
    {
        dp[1][i] = max(dp[1][i-1], dp[0][i-1] + a[i]);
        dp[0][i] = max(dp[0][i-1], dp[1][i-1] - a[i]);
    }
    printf("%d\n", max(dp[0][P], dp[1][P]));
    return 0;
}

/**************************************************

filename :f.cpp

author :maksyuki

created time :2017/3/4 10:34:52

last modified :2017/3/4 11:02:52

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CPPFF ifstream cin ("in")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 66666;

int a[maxn], dp[2][maxn];

int main()

{

//CFF;

//CPPFF;

int P;

scanf("%d", &P);

for(int i = 1; i <= P; i++)

scanf("%d", &a[i]);

for(int i = 0; i < maxn; i++)

dp[0][i] = dp[1][i] = -INF;

dp[0][0] = 0;

for(int i = 1; i <= P; i++)

{

dp[1][i] = max(dp[1][i-1], dp[0][i-1] + a[i]);

dp[0][i] = max(dp[0][i-1], dp[1][i-1] - a[i]);

}

printf("%d\n", max(dp[0][P], dp[1][P]));

return 0;

}

poj1953

maksyuki 发表于 oj 分类，标签: DP-线性DP

03 3月 2017

World Cup Noise
"KO-RE-A, KO-RE-A" shout 54.000 happy football fans after their team has reached the semifinals of the FIFA World Cup in their home country. But although their excitement is real, the Korean people are still very organized by nature. For example, they have organized huge trumpets (that sound like blowing a ship's horn) to support their team playing on the field. The fans want to keep the level of noise constant throughout the match.
The trumpets are operated by compressed gas. However, if you blow the trumpet for 2 seconds without stopping it will break. So when the trumpet makes noise, everything is okay, but in a pause of the trumpet,the fans must chant "KO-RE-A"!
Before the match, a group of fans gathers and decides on a chanting pattern. The pattern is a sequence of 0's and 1's which is interpreted in the following way: If the pattern shows a 1, the trumpet is blown. If it shows a 0, the fans chant "KO-RE-A". To ensure that the trumpet will not break, the pattern is not allowed to have two consecutive 1's in it.
Problem
Given a positive integer n, determine the number of different chanting patterns of this length, i.e., determine the number of n-bit sequences that contain no adjacent 1's. For example, for n = 3 the answer is 5 (sequences 000, 001, 010, 100, 101 are acceptable while 011, 110, 111 are not).

Input

The first line contains the number of scenarios.
For each scenario, you are given a single positive integer less than 45 on a line by itself.

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the number of n-bit sequences which have no adjacent 1's. Terminate the output for the scenario with a blank line.

Sample Input

Sample Output

Scenario #1:

Scenario #2:

Source

TUD Programming Contest 2002, Darmstadt, Germany

题目类型：线性DP

算法分析：dp[0][i]表示以0结尾的长度为i的串的方案数，dp[1][i]表示以1结尾的长度为i的串的方案数，初始化dp[0][1] = dp[1][1] = 1，状态转移方程为dp[0][i] = dp[0][i-1] + dp[1][i-1]，dp[1][i] = dp[0][i-1]，最后查表输出dp[0][n] + dp[1][n]即可

/**************************************************
filename       :e.cpp
author         :maksyuki
created time   :2017/3/3 20:30:09
last modified  :2017/3/3 20:38:03
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CPPFF ifstream cin ("in")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int dp[2][66];

int main()
{
    //CFF;
    //CPPFF;
    int id = 1;
    dp[0][1] = dp[1][1] = 1;
    for(int i = 2; i <= 50; i++)
    {
        dp[0][i] = dp[0][i-1] + dp[1][i-1];
        dp[1][i] = dp[0][i-1];
    }

    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        printf("Scenario #%d:\n", id++);
        printf("%d\n\n", dp[0][n] + dp[1][n]);
    }
    return 0;
}

/**************************************************

filename :e.cpp

author :maksyuki

created time :2017/3/3 20:30:09

last modified :2017/3/3 20:38:03

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CPPFF ifstream cin ("in")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int dp[2][66];

int main()

{

//CFF;

//CPPFF;

int id = 1;

dp[0][1] = dp[1][1] = 1;

for(int i = 2; i <= 50; i++)

{

dp[0][i] = dp[0][i-1] + dp[1][i-1];

dp[1][i] = dp[0][i-1];

}

int t;

scanf("%d", &t);

while(t--)

{

int n;

scanf("%d", &n);

printf("Scenario #%d:\n", id++);

printf("%d\n\n", dp[0][n] + dp[1][n]);

}

return 0;

}

poj1664

maksyuki 发表于 oj 分类，标签: DP-线性DP

03 3月 2017

放苹果

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input 阅读全文 »

poj1414

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

03 3月 2017

Life Line

Let's play a new board game "Life Line". The number of the players is greater than 1 and less than 10. In this game, the board is a regular triangle in which many small regular triangles are arranged (See Figure 1). The edges of each small triangle are of the same length.

The size of the board is expressed by the number of vertices on the bottom edge of the outer triangle.For example, the size of the board in Figure 1 is 4.

At the beginning of the game, each player is assigned his own identification number between 1 and 9,and is given some stones on which his identification number is written.

Each player puts his stone in turn on one of the "empty" vertices. An "empty vertex" is a vertex that has no stone on it.

When one player puts his stone on one of the vertices during his turn, some stones might be removed from the board. The player gains points which is equal to the number of the removed stones of himself. The points of a player for a single turn is the points he gained minus the points he lost in that turn.

The conditions for removing stones are as follows :

1.The stones on the board are divided into groups. Each group contains a set of stones whose numbersare the same and placed adjacently. That is, if the same numbered stones are placed adjacently,they belong to the same group.

2.If none of the stones in a group is adjacent to at least one "empty" vertex, all the stones in that group are removed from the board.

Figure 2 shows an example of the groups of stones.

Suppose that the turn of the player '4' comes now. If he puts his stone on the vertex shown in Figure 3a, the conditions will be satisfied to remove some groups of stones (shadowed in Figure 3b). The player gains 6 points, because the 6 stones of others are removed from the board (See Figure 3c).

As another example, suppose that the turn of the player '2' comes in Figure 2. If the player puts his

stone on the vertex shown in Figure 4a, the conditions will be satisfied to remove some groups of stones (shadowed in Figure 4b). The player gains 4 points, because the 4 stones of others are removed. But, at the same time, he loses 3 points, because his 3 stones are removed. As the result, the player's points of this turn is 4 ? 3 = 1 (See Figure 4c).

When each player puts all of his stones on the board, the game is over. The total score of a player is the summation of the points of all of his turns.

Your job is to write a program that tells you the maximum points a player can get (i.e., the points he gains - the points he loses) in his current turn.

Input

The input consists of multiple data. Each data represents the state of the board of the game still in

progress. The format of each data is as follows.

N C
S_1,1
S_2,1 S_2,2
S_3,1 S_3,2 S_3,3
. . .
S_N,1 . . . S_N,N

N is the size of the board (3 <= N <= 10). C is the identification number of the player whose turn comes now (1 <= C <= 9). That is, your program must calculate his points in this turn. S_i,j is the state of the vertex on the board (0 <= Si,j <= 9). If the value of Si,j is positive, it means that there is the stone numbered by Si,j there. If the value of S_i,j is 0, it means that the vertex is "empty". Two zeros in a line, i.e., 0 0, represents the end of the input.

Output

For each data, the maximum points the player can get in the turn should be output, each in a separate line.

Sample Input

4 4
2
2 3
1 0 4
1 1 4 0
4 5
2
2 3
3 0 4
1 1 4 0
4 1
2
2 3
3 0 4
1 1 4 0
4 1
1
1 1
1 1 1
1 1 1 0
4 2
1
1 1
1 1 1
1 1 1 0
4 1
0
2 2
5 0 7
0 5 7 0
4 2
0
0 3
1 0 4
0 1 0 4
4 3
0
3 3
3 2 3
0 3 0 3
4 2
0
3 3
3 2 3
0 3 0 3
6 1
1
1 2
1 1 0
6 7 6 8
0 7 6 8 2
6 6 7 2 2 0
5 9
0
0 0
0 0 0
0 0 0 0
0 0 0 0 0
5 3
3
3 2
4 3 2
4 4 0 3
3 3 3 0 3
0 0

Sample Output

6
5
1
-10
8
-1
0
1
-1
5
0
5

Source

Japan 2002 Kanazawa

题目类型：简单搜索

算法分析：直接以每次"0"为起点搜索计算同时更新最大值即可

/**************************************************
filename       :c.cpp
author         :maksyuki
created time   :2017/3/3 12:08:02
last modified  :2017/3/3 16:36:03
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CPPFF ifstream cin ("in")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 66;

int N, C;
int g[maxn][maxn];
bool vis[maxn][maxn];
bool is_adj;

const int dx[] = {1, -1, 0, 0, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1};

struct node
{
    int x, y;
    node(int xx, int yy): x(xx), y(yy) {}
};

bool Ok(int x, int y, int val)
{
    if(x >= 1 && x <= N && y >= 1 && y <= N && g[x][y] != INF && !vis[x][y])
    {
        if(g[x][y] == val) return true;
        if(!g[x][y]) is_adj = true;
    }
    return false;
}

int bfs(int x0, int y0)
{
    queue<node> qu;
    vis[x0][y0] = true;
    qu.push(node(x0, y0));

    is_adj = false;
    int res = 1;
    while(!qu.empty())
    {
        node tt = qu.front(); qu.pop();
        for(int i = 0; i < 6; i++)
        {
            int tmpx = tt.x + dx[i];
            int tmpy = tt.y + dy[i];

            if(Ok(tmpx, tmpy, g[x0][y0]))
            {
                vis[tmpx][tmpy] = true;
                qu.push(node(tmpx, tmpy));
                res++;
            }
        }
    }
    if(is_adj) return 0;
    return res;
}

int main()
{
    //CFF;
    //CPPFF;
    while(scanf("%d%d", &N, &C) != EOF)
    {
        if(!N && !C) break;
        
        for(int i = 0; i < maxn; i++)
            for(int j = 0; j < maxn; j++)
                g[i][j] = INF;

        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= i; j++)
                scanf("%d", &g[i][j]);

        int maxval = -INF;
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= i; j++)
                if(g[i][j] == 0)
                {
                    g[i][j] = C;
                    int tmp = 0;
                    memset(vis, false, sizeof(vis));
                    for(int k = 1; k <= N; k++)
                        for(int q = 1; q <= k; q++)
                            if(!vis[k][q] && g[k][q] > 0 && g[k][q] != C)
                                tmp += bfs(k, q);
                    tmp -= bfs(i, j);
                    maxval = max(maxval, tmp);
                    g[i][j] = 0;
                }
        
        printf("%d\n", maxval);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

/**************************************************

filename :c.cpp

author :maksyuki

created time :2017/3/3 12:08:02

last modified :2017/3/3 16:36:03

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CPPFF ifstream cin ("in")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 66;

int N, C;

int g[maxn][maxn];

bool vis[maxn][maxn];

bool is_adj;

const int dx[] = {1, -1, 0, 0, -1, 1};

const int dy[] = {0, 0, 1, -1, -1, 1};

struct node

{

int x, y;

node(int xx, int yy): x(xx), y(yy) {}

};

bool Ok(int x, int y, int val)

{

if(x >= 1 && x <= N && y >= 1 && y <= N && g[x][y] != INF && !vis[x][y])

{

if(g[x][y] == val) return true;

if(!g[x][y]) is_adj = true;

}

return false;

}

int bfs(int x0, int y0)

{

queue<node> qu;

vis[x0][y0] = true;

qu.push(node(x0, y0));

is_adj = false;

int res = 1;

while(!qu.empty())

{

node tt = qu.front(); qu.pop();

for(int i = 0; i < 6; i++)

{

int tmpx = tt.x + dx[i];

int tmpy = tt.y + dy[i];

if(Ok(tmpx, tmpy, g[x0][y0]))

{

vis[tmpx][tmpy] = true;

qu.push(node(tmpx, tmpy));

res++;

}

if(is_adj) return 0;

return res;

}

int main()

{

//CFF;

//CPPFF;

while(scanf("%d%d", &N, &C) != EOF)

{

if(!N && !C) break;

for(int i = 0; i < maxn; i++)

for(int j = 0; j < maxn; j++)

g[i][j] = INF;

for(int i = 1; i <= N; i++)

for(int j = 1; j <= i; j++)

scanf("%d", &g[i][j]);

int maxval = -INF;

for(int i = 1; i <= N; i++)

for(int j = 1; j <= i; j++)

if(g[i][j] == 0)

{

g[i][j] = C;

int tmp = 0;

memset(vis, false, sizeof(vis));

for(int k = 1; k <= N; k++)

for(int q = 1; q <= k; q++)

if(!vis[k][q] && g[k][q] > 0 && g[k][q] != C)

tmp += bfs(k, q);

tmp -= bfs(i, j);

maxval = max(maxval, tmp);

g[i][j] = 0;

}

printf("%d\n", maxval);

}

return 0;

}

poj1179

maksyuki 发表于 oj 分类，标签: DP-区间DP

03 3月 2017

Polygon

Polygon is a game for one player that starts on a polygon with N vertices, like the one in Figure 1, where N=4. Each vertex is labelled with an integer and each edge is labelled with either the symbol + (addition) or the symbol * (product). The edges are numbered from 1 to N.
On the first move, one of the edges is removed. Subsequent moves involve the following steps:
�pick an edge E and the two vertices V1 and V2 that are linked by E; and
�replace them by a new vertex, labelled with the result of performing the operation indicated in E on the labels of V1 and V2.
The game ends when there are no more edges, and its score is the label of the single vertex remaining.

Consider the polygon of Figure 1. The player started by removing edge 3. After that, the player picked edge 1, then edge 4, and, finally, edge 2. The score is 0.
Write a program that, given a polygon, computes the highest possible score and lists all the edges that, if removed on the first move, can lead to a game with that score.

Input

Your program is to read from standard input. The input describes a polygon with N vertices. It contains two lines. On the first line is the number N. The second line contains the labels of edges 1, ..., N, interleaved with the vertices' labels (first that of the vertex between edges 1 and 2, then that of the vertex between edges 2 and 3, and so on, until that of the vertex between edges N and 1), all separated by one space. An edge label is either the letter t (representing +) or the letter x (representing *).

3 <= N <= 50
For any sequence of moves, vertex labels are in the range [-32768,32767].

Output

Your program is to write to standard output. On the first line your program must write the highest score one can get for the input polygon. On the second line it must write the list of all edges that, if removed on the first move, can lead to a game with that score. Edges must be written in increasing order, separated by one space.

Sample Input

t -7 t 4 x 2 x 5

Sample Output

1 2

Source

IOI 1998

题目类型：区间DP

算法分析：dp1[i][j]表示区间[i,j]之间的点合并后的最大值，初始化dp1[i][i] = a[i]，状态转移方程为dp1[i][j] = max(dp1[i][j], dp1[i][q] op dp1[q+1][j] op dp2[i][q] op dp2[q+1][j])，由于最大值有可能是从两个最小值(负数)相乘得到，所以还需要维护区间的最小值dp2[i][j]，转移方程和dp1类似，注意dp2有可能是最小值(负数)和最大值相乘得到，所以更新dp2时也要考虑到。计算过程为每次删除一条边然后计算一次最大值并记录，最后递增遍历一遍并输出最大值对应的下标即可

/**************************************************
filename       :b.cpp
author         :maksyuki
created time   :2017/3/2 20:16:22
last modified  :2017/3/3 11:35:17
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CPPFF ifstream cin ("in")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 100 + 6;

int a[maxn], dp1[maxn][maxn], dp2[maxn][maxn], ans[maxn];
char op[maxn][maxn];

int Op(int a, int b, char val, int c, int d, int flag)
{
    if(val == 't') return a + b;
    else
    {
        if(flag == 1) return max(a * b, c * d);
        else return min(a * b, c * d);
    }
}

int main()
{
    //CFF;
    //CPPFF;
    int n;
    while(scanf("%d", &n) != EOF)
    {
        char tmp;
        for(int i = 1; i <= n; i++)
        {
            scanf(" %c %d", &tmp, &a[i]);
            a[i+n] = a[i];

            if(i == 1)
            {
                op[i][n] = op[n][i] = tmp;
                op[n][n+1] = op[n+1][n] = tmp;    
            }
            else
            {
                op[i-1][i] = op[i][i-1] = tmp;    
                op[i-1+n][i+n] = op[i+n][i-1+n] = tmp;
            }
        }
        
        for(int i = 0; i < maxn; i++)
            ans[i] = -INF;

        for(int k = 0; k <= n - 1; k++)
        {
            for(int i = 0; i < maxn; i++)
                for(int j = 0; j < maxn; j++)
                {
                    dp1[i][j] = -INF;
                    dp2[i][j] = INF; 
                }

            for(int i = 1 + k; i <= n + k; i++)
                dp1[i][i] = dp2[i][i] = a[i];

            for(int len = 1; len <= n; len++)
                for(int i = 1 + k; i <= n + k; i++)
                {
                    int j = i + len;
                    if(j > n + k) break;
                    for(int q = i; q <= j - 1; q++)
                    {
                        dp1[i][j] = max(dp1[i][j], Op(dp1[i][q], dp1[q+1][j], op[q][q+1], dp2[i][q], dp2[q+1][j], 1));
                        dp2[i][j] = min(dp2[i][j], Op(dp2[i][q], dp2[q+1][j], op[q][q+1], dp1[i][q], dp2[q+1][j], 2)); 
                        dp2[i][j] = min(dp2[i][j], Op(dp2[i][q], dp2[q+1][j], op[q][q+1], dp2[i][q], dp1[q+1][j], 2)); 
                    }
                }
            ans[k+1] = dp1[1+k][n+k]; 
        }

        int maxval = -INF;
        for(int i = 1; i <= n; i++)
            maxval = max(maxval, ans[i]);
        
        printf("%d\n", maxval);
        bool is_first = true;
        for(int i = 1; i <= n; i++)
        {
            if(maxval == ans[i])
            {
                if(is_first)
                {
                    is_first = false;
                    printf("%d", i);
                }
                else
                    printf(" %d", i);
            }
        }
        puts("");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

/**************************************************

filename :b.cpp

author :maksyuki

created time :2017/3/2 20:16:22

last modified :2017/3/3 11:35:17

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CPPFF ifstream cin ("in")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100 + 6;

int a[maxn], dp1[maxn][maxn], dp2[maxn][maxn], ans[maxn];

char op[maxn][maxn];

int Op(int a, int b, char val, int c, int d, int flag)

{

if(val == 't') return a + b;

else

{

if(flag == 1) return max(a * b, c * d);

else return min(a * b, c * d);

}

int main()

{

//CFF;

//CPPFF;

int n;

while(scanf("%d", &n) != EOF)

{

char tmp;

for(int i = 1; i <= n; i++)

{

scanf(" %c %d", &tmp, &a[i]);

a[i+n] = a[i];

if(i == 1)

{

op[i][n] = op[n][i] = tmp;

op[n][n+1] = op[n+1][n] = tmp;

}

else

{

op[i-1][i] = op[i][i-1] = tmp;

op[i-1+n][i+n] = op[i+n][i-1+n] = tmp;

}

for(int i = 0; i < maxn; i++)

ans[i] = -INF;

for(int k = 0; k <= n - 1; k++)

{

for(int i = 0; i < maxn; i++)

for(int j = 0; j < maxn; j++)

{

dp1[i][j] = -INF;

dp2[i][j] = INF;

}

for(int i = 1 + k; i <= n + k; i++)

dp1[i][i] = dp2[i][i] = a[i];

for(int len = 1; len <= n; len++)

for(int i = 1 + k; i <= n + k; i++)

{

int j = i + len;

if(j > n + k) break;

for(int q = i; q <= j - 1; q++)

{

dp1[i][j] = max(dp1[i][j], Op(dp1[i][q], dp1[q+1][j], op[q][q+1], dp2[i][q], dp2[q+1][j], 1));

dp2[i][j] = min(dp2[i][j], Op(dp2[i][q], dp2[q+1][j], op[q][q+1], dp1[i][q], dp2[q+1][j], 2));

dp2[i][j] = min(dp2[i][j], Op(dp2[i][q], dp2[q+1][j], op[q][q+1], dp2[i][q], dp1[q+1][j], 2));

}

ans[k+1] = dp1[1+k][n+k];

}

int maxval = -INF;

for(int i = 1; i <= n; i++)

maxval = max(maxval, ans[i]);

printf("%d\n", maxval);

bool is_first = true;

for(int i = 1; i <= n; i++)

{

if(maxval == ans[i])

{

if(is_first)

{

is_first = false;

printf("%d", i);

}

else

printf(" %d", i);

}

puts("");

}

return 0;

}

超客的水墨烟雨

poj2181

poj1953

poj1664

poj1414

poj1179

分类目录

标签云

书签

近期评论

2017年3月
一	二	三	四	五	六	日
« 2月				12月 »
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31