BestCoder Round #67 (2/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

26 12月 2015

A N bulbs

Problem Description

N bulbs are in a row from left to right,some are on, and some are off.The first bulb is the most left one. And the last one is the most right one.they are numbered from 1 to n,from left to right. 阅读全文 »

Codeforces Round #336(Div.2) (1/5) (Div.1) (0/5)

maksyuki 发表于比赛分类，标签: 比赛-codeforces

26 12月 2015

A Saitama Destroys Hotel

Saitama accidentally destroyed a hotel again. To repay the hotel company, Genos has volunteered to operate an elevator in one of its other hotels. The elevator is special — it starts on the top floor, can only move down, and has infinite capacity. Floors are numbered from 0 to s and elevator initially starts on floor s at time 0.

The elevator takes exactly 1 second to move down exactly 1 floor and negligible time to pick up passengers. Genos is given a list detailing when and on which floor passengers arrive. Please determine how long in seconds it will take Genos to bring all passengers to floor 0.

Input

The first line of input contains two integers n and s (1 ≤ n ≤ 100, 1 ≤ s ≤ 1000) — the number of passengers and the number of the top floor respectively.

The next n lines each contain two space-separated integers f_i and t_i (1 ≤ f_i ≤ s, 1 ≤ t_i ≤ 1000) — the floor and the time of arrival in seconds for the passenger number i.

Output

Print a single integer — the minimum amount of time in seconds needed to bring all the passengers to floor 0.

Sample test(s)

input

3 7
2 1
3 8
5 2

output

input

5 10
2 77
3 33
8 21
9 12
10 64

output

Note

In the first sample, it takes at least 11 seconds to bring all passengers to floor 0. Here is how this could be done:

Move to floor 5: takes 2seconds.
Pick up passenger 3.
Move to floor 3: takes 2seconds.
Wait for passenger 2to arrive: takes 4seconds.
Pick up passenger 2.
Go to floor 2: takes 1second.
Pick up passenger 1.
Go to floor 0: takes 2seconds.

This gives a total of 2 + 2 + 4 + 1 + 2 = 11 seconds.

题目类型：简单模拟

算法分析：先按照楼层排序，最后从上到下模拟计算即可

/*************************************************
Author        :supermaker
Created Time  :2015/12/24 0:11:13
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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;

struct node
{
    int a, b;
};

bool operator < (const node &a, const node &b)
{
    return a.a < b.a;
};

node aa[maxn];

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

        sort (aa + 1, aa + 1 + n);
        LL res = 0, tt = 0;
        aa[n+1].a = s, aa[n+1].b = 0;
        aa[0].a = 0, aa[0].b = 0;
        for (int i = n + 1; i >= 1; i--)
        {
            res += aa[i].a - aa[i-1].a;
            tt += aa[i].a - aa[i-1].a;
            if (tt < aa[i-1].b)
            {   
                res += aa[i-1].b - tt;
                int ta = aa[i-1].b - tt;
                tt += ta;
            }
        }
        printf ("%I64d\n", res);
    }
    return 0;
}

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

Author :supermaker

Created Time :2015/12/24 0:11:13

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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;

struct node

{

int a, b;

};

bool operator < (const node &a, const node &b)

{

return a.a < b.a;

};

node aa[maxn];

int main()

{

//CFF;

//CPPFF;

int n, s;

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

{

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

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

sort (aa + 1, aa + 1 + n);

LL res = 0, tt = 0;

aa[n+1].a = s, aa[n+1].b = 0;

aa[0].a = 0, aa[0].b = 0;

for (int i = n + 1; i >= 1; i--)

{

res += aa[i].a - aa[i-1].a;

tt += aa[i].a - aa[i-1].a;

if (tt < aa[i-1].b)

{

res += aa[i-1].b - tt;

int ta = aa[i-1].b - tt;

tt += ta;

}

printf ("%I64d\n", res);

}

return 0;

}

TopCoder SRM#676(Div2)(2/3)

maksyuki 发表于比赛分类，标签: 比赛-topcoder

19 12月 2015

250 Problem Statement

Farmer John recently found out about a popular online farming game.There are n types of plants in the game. The types are numbered 0 through n-1. At the beginning of the game, Farmer John is given one seed of each plant type.There is a single plot of land. At any time the plot can only contain at most one plant. Whenever the plot is empty, Farmer John can plant one of the seeds. Once a seed of type i is planted, it takes time[i] seconds until it grows into a fully developed plant. When that happens, Farmer John will harvest the plant and the plot will become empty again. Planting a seed and harvesting a plant happens instanteously.
Farmer John also has budget coins. He can spend these coins to make his plants grow faster. For each i, Farmer John may pay cost[i] coins to reduce time[i] by 1. Farmer John may pay for the same plant multiple times, each time decreasing its growing time by 1. Obviously, the growing time cannot be reduced below 0.
You are given the vector <int>s time and cost with n elements each, and the int budget. Determine and return the minimum amount of time in which Farmer John can grow a single plant of each type.
Definition

Class:
FarmvilleDiv2
Method:
minTime
Parameters:
vector <int>, vector <int>, int
Returns:
int
Method signature:
int minTime(vector <int> time, vector <int> cost, int budget)
(be sure your method is public)

题目类型：贪心

算法分析：先将cost值低的时间消去，注意每次消去时要将当前值减去！！！

// BEGIN CUT HERE

// END CUT HERE
#line 5 "FarmvilleDiv2.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;

#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned long long

#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
//typedef long long LL;
typedef pair<int,int> PII;

struct node
{
    int x, y;
};

bool cmp (node a, node b) {return a.y < b.y;}

node aa[66];

class FarmvilleDiv2
{
        public:
        int minTime(vector <int> time, vector <int> cost, int budget)
        {
            int n = time.size ();
            for (int i = 0; i < n; i++)
                aa[i].x = time[i];

            for (int i = 0; i < n; i++)
                aa[i].y = cost[i];

            sort (aa, aa + n, cmp);
            int res = 0;
            bool is_first = true;
            for (int i = 0; i < n; )
            {
                if (i < n && budget >= aa[i].x * aa[i].y)
                {
                    while (i < n && budget >= aa[i].x * aa[i].y)
                    {
                        budget -= aa[i].x * aa[i].y;
                        i++;
                    }

                }

                else if (i < n)
                {
                    if (is_first)
                    {
                        res += aa[i].x - (budget / aa[i].y);
                        budget = budget - (budget / aa[i].y) * aa[i].y;
                        is_first = false;
                    }

                    else
                    {
                        res += aa[i].x;
                    }

                    i++;
                }
            }
            return res;
        }

// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { int Arr0[] = {100}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 26; int Arg3 = 74; verify_case(0, Arg3, minTime(Arg0, Arg1, Arg2)); }
	void test_case_1() { int Arr0[] = {100}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 101; int Arg3 = 0; verify_case(1, Arg3, minTime(Arg0, Arg1, Arg2)); }
	void test_case_2() { int Arr0[] = {2,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 3; int Arg3 = 0; verify_case(2, Arg3, minTime(Arg0, Arg1, Arg2)); }
	void test_case_3() { int Arr0[] = {1,2,3,4,5}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {5,4,3,2,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 15; int Arg3 = 6; verify_case(3, Arg3, minTime(Arg0, Arg1, Arg2)); }
	void test_case_4() { int Arr0[] = {100,100,100,100,100,100,100,100,100,100}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {2,4,6,8,10,1,3,5,7,9}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 5000; int Arg3 = 50; verify_case(4, Arg3, minTime(Arg0, Arg1, Arg2)); }
	void test_case_5() { int Arr0[] = {30,40,20,10}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {10,20,30,40}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 5; int Arg3 = 100; verify_case(5, Arg3, minTime(Arg0, Arg1, Arg2)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
        FarmvilleDiv2 ___test;
        ___test.run_test(-1);
        return 0;
}
// END CUT HERE

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

// BEGIN CUT HERE

// END CUT HERE

#line 5 "FarmvilleDiv2.cpp"

#include <cstdlib>

#include <cctype>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <string>

#include <iostream>

#include <sstream>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <fstream>

#include <numeric>

#include <iomanip>

#include <bitset>

#include <list>

#include <stdexcept>

#include <functional>

#include <utility>

#include <ctime>

using namespace std;

#define PB push_back

#define MP make_pair

#define LL long long

#define ULL unsigned long long

#define REP(i,n) for(i=0;i<(n);++i)

#define FOR(i,l,h) for(i=(l);i<=(h);++i)

#define FORD(i,h,l) for(i=(h);i>=(l);--i)

typedef vector<int> VI;

typedef vector<string> VS;

typedef vector<double> VD;

//typedef long long LL;

typedef pair<int,int> PII;

struct node

{

int x, y;

};

bool cmp (node a, node b) {return a.y < b.y;}

node aa[66];

class FarmvilleDiv2

{

public:

int minTime(vector <int> time, vector <int> cost, int budget)

{

int n = time.size ();

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

aa[i].x = time[i];

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

aa[i].y = cost[i];

sort (aa, aa + n, cmp);

int res = 0;

bool is_first = true;

for (int i = 0; i < n; )

{

if (i < n && budget >= aa[i].x * aa[i].y)

{

while (i < n && budget >= aa[i].x * aa[i].y)

{

budget -= aa[i].x * aa[i].y;

i++;

}

else if (i < n)

{

if (is_first)

{

res += aa[i].x - (budget / aa[i].y);

budget = budget - (budget / aa[i].y) * aa[i].y;

is_first = false;

}

else

{

res += aa[i].x;

}

i++;

}

return res;

}

// BEGIN CUT HERE

public:

void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }

private:

template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

void test_case_0() { int Arr0[] = {100}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 26; int Arg3 = 74; verify_case(0, Arg3, minTime(Arg0, Arg1, Arg2)); }

void test_case_1() { int Arr0[] = {100}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 101; int Arg3 = 0; verify_case(1, Arg3, minTime(Arg0, Arg1, Arg2)); }

void test_case_2() { int Arr0[] = {2,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 3; int Arg3 = 0; verify_case(2, Arg3, minTime(Arg0, Arg1, Arg2)); }

void test_case_3() { int Arr0[] = {1,2,3,4,5}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {5,4,3,2,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 15; int Arg3 = 6; verify_case(3, Arg3, minTime(Arg0, Arg1, Arg2)); }

void test_case_4() { int Arr0[] = {100,100,100,100,100,100,100,100,100,100}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {2,4,6,8,10,1,3,5,7,9}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 5000; int Arg3 = 50; verify_case(4, Arg3, minTime(Arg0, Arg1, Arg2)); }

void test_case_5() { int Arr0[] = {30,40,20,10}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {10,20,30,40}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 5; int Arg3 = 100; verify_case(5, Arg3, minTime(Arg0, Arg1, Arg2)); }

// END CUT HERE

};

// BEGIN CUT HERE

int main()

{

FarmvilleDiv2 ___test;

___test.run_test(-1);

return 0;

}

// END CUT HERE

550 Problem Statement

Alice and Bob have a rectangular board divided into a grid with r rows and c columns. The grid is described by the vector <string> s. Each character of s represents one cell. There are four types of cells:

'E' denotes an exit. There may be arbitrarily many exits, possibly zero.
'T' means the square contains a single token. Initially there will be exactly one token on the entire board.
'#' denotes an obstacle.
'.' denotes an empty cell.
Alice and Bob will play a game on this board. The game is parameterized by the int k. The token initially has the number k on it. The players will take alternating turns, starting with Alice. A player's turn consists of the following steps:

The player moves the token one square up, down, left, or right. The token cannot go over the edge of the board and it cannot enter a cell with an obstacle.
If this token is on an exit, it disappears from the board.
Otherwise, subtract one from the number on the token. If the number on the token is zero, remove it from the board.
The first player unable to make a move loses the game. (This happens when the token is stuck and also when it already left the board.)

You are given the vector <string> s and the int k Compute the winner of the game, assuming both Alice and Bob play optimally. Return the winner's name: either "Alice" or "Bob". Note that the return value is case-sensitive.

Definition
Class: BoardEscapeDiv2
Method: findWinner
Parameters: vector <string>, int
Returns: string
Method signature: string findWinner(vector <string> s, int k)
(be sure your method is public)

题目类型：博弈(记忆化搜索)

算法分析：对于完全信息的博弈问题，求解过程需要在一个博弈树上进行dfs遍历并在回溯时计算当前节点的估价值并选择对于自己来说最好的那个状态。这里设定估价值"1"表示对当前节点好的值，"0"表示对当前节点不好的值。回溯时判断当前节点的所有子节点的估价值，若所有子节点的估价值都是"1"，则当前节点的估价值为"0"。否则，当前节点的估价值为"1"。对于计算过的值使用数组dp存下来节省时间开销

// BEGIN CUT HERE

// END CUT HERE
#line 5 "BoardEscapeDiv2.cpp"
#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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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[66][66][166];
int n, m;
vector <string> g;

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

class BoardEscapeDiv2
{
        public:
		int dfs (int x, int y, int k)
		{
			if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '#') return 1;
			if (g[x][y] == 'E' || k == 0) return 0;
			if (dp[x][y][k] != -1) return dp[x][y][k];
			for (int i = 0; i < 4; i++)
				if (!dfs (x + dx[i], y + dy[i], k - 1))
					return dp[x][y][k] = 1;
			return dp[x][y][k] = 0;
		}

        string findWinner(vector <string> s, int k)
        {
			n = s.size (), m = s[0].size ();
			g = s;
			memset (dp, -1, sizeof (dp));
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					if (g[i][j] == 'T')
					{
						g[i][j] = '.';
						int win = dfs (i, j, k);
						if (win) return string ("Alice");
						else  return string ("Bob");
					}
        }
        
// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arr0[] = {"T.#",
 "#.E"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; string Arg2 = "Alice"; verify_case(0, Arg2, findWinner(Arg0, Arg1)); }
	void test_case_1() { string Arr0[] = {"E#E",
 "#T#",
 "E#E"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 99; string Arg2 = "Bob"; verify_case(1, Arg2, findWinner(Arg0, Arg1)); }
	void test_case_2() { string Arr0[] = {"#E...",
 "#...E",
 "E.T#.",
 "..#.."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 13; string Arg2 = "Alice"; verify_case(2, Arg2, findWinner(Arg0, Arg1)); }
	void test_case_3() { string Arr0[] = {"TE"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 50; string Arg2 = "Alice"; verify_case(3, Arg2, findWinner(Arg0, Arg1)); }
	void test_case_4() { string Arr0[] = {".T."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; string Arg2 = "Alice"; verify_case(4, Arg2, findWinner(Arg0, Arg1)); }
	void test_case_5() { string Arr0[] = {"..........................",
 "......EEE..EEE..E...E.....",
 ".....E.....E..E.EE.EE.....",
 "......EEE..EEE..E.E.E.....",
 ".........E.E.E..E...E.....",
 "......EEE..E..E.E...E.....",
 "..........................",
 "...E#E#E#E#E#E#E#E#E#E#...",
 "..........................",
 "......EEE..EEE...EEE......",
 ".....E........E.E.........",
 "......EEE.....E..EEE......",
 ".....E...E...E..E...E.....",
 "......EEE....E...EEE......",
 "..........................",
 "...#E#E#E#E#E#E#E#E#E#E...",
 "..........................",
 "....EE...E...E..E.EEE.E...",
 "...E.....E...E..E.E...E...",
 "...E.EE..E...EEEE.EE..E...",
 "...E..E..E...E..E.E.......",
 "....EE...EEE.E..E.E...E...",
 "T........................."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 100; string Arg2 = "Bob"; verify_case(5, Arg2, findWinner(Arg0, Arg1)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
        BoardEscapeDiv2 ___test;
        ___test.run_test(-1);
        return 0;
}
// END CUT HERE

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

// BEGIN CUT HERE

// END CUT HERE

#line 5 "BoardEscapeDiv2.cpp"

#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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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[66][66][166];

int n, m;

vector <string> g;

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

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

class BoardEscapeDiv2

{

public:

int dfs (int x, int y, int k)

{

if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '#') return 1;

if (g[x][y] == 'E' || k == 0) return 0;

if (dp[x][y][k] != -1) return dp[x][y][k];

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

if (!dfs (x + dx[i], y + dy[i], k - 1))

return dp[x][y][k] = 1;

return dp[x][y][k] = 0;

}

string findWinner(vector <string> s, int k)

{

n = s.size (), m = s[0].size ();

g = s;

memset (dp, -1, sizeof (dp));

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

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

if (g[i][j] == 'T')

{

g[i][j] = '.';

int win = dfs (i, j, k);

if (win) return string ("Alice");

else return string ("Bob");

}

// BEGIN CUT HERE

public:

private:

void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

void test_case_0() { string Arr0[] = {"T.#",

"#.E"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; string Arg2 = "Alice"; verify_case(0, Arg2, findWinner(Arg0, Arg1)); }

void test_case_1() { string Arr0[] = {"E#E",

"#T#",

"E#E"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 99; string Arg2 = "Bob"; verify_case(1, Arg2, findWinner(Arg0, Arg1)); }

void test_case_2() { string Arr0[] = {"#E...",

"#...E",

"E.T#.",

"..#.."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 13; string Arg2 = "Alice"; verify_case(2, Arg2, findWinner(Arg0, Arg1)); }

void test_case_3() { string Arr0[] = {"TE"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 50; string Arg2 = "Alice"; verify_case(3, Arg2, findWinner(Arg0, Arg1)); }

void test_case_4() { string Arr0[] = {".T."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; string Arg2 = "Alice"; verify_case(4, Arg2, findWinner(Arg0, Arg1)); }

void test_case_5() { string Arr0[] = {"..........................",

"......EEE..EEE..E...E.....",

".....E.....E..E.EE.EE.....",

"......EEE..EEE..E.E.E.....",

".........E.E.E..E...E.....",

"......EEE..E..E.E...E.....",

"..........................",

"...E#E#E#E#E#E#E#E#E#E#...",

"..........................",

"......EEE..EEE...EEE......",

".....E........E.E.........",

"......EEE.....E..EEE......",

".....E...E...E..E...E.....",

"......EEE....E...EEE......",

"..........................",

"...#E#E#E#E#E#E#E#E#E#E...",

"..........................",

"....EE...E...E..E.EEE.E...",

"...E.....E...E..E.E...E...",

"...E.EE..E...EEEE.EE..E...",

"...E..E..E...E..E.E.......",

"....EE...EEE.E..E.E...E...",

"T........................."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 100; string Arg2 = "Bob"; verify_case(5, Arg2, findWinner(Arg0, Arg1)); }

// END CUT HERE

};

// BEGIN CUT HERE

int main()

{

BoardEscapeDiv2 ___test;

___test.run_test(-1);

return 0;

}

// END CUT HERE

poj2182

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

16 12月 2015

Lost Cows

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

Input

* Line 1: A single integer, N

* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

Output

* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

Sample Input

5
1
2
1
0

Sample Output

Source

USACO 2003 U S Open Orange

题目类型：动态第k大查询

算法分析：从后向前确定每个数，可知当前数(输入值为k)是还未确定数中的第k + 1大的数，则可以维护一个线段树来动态查找

/*************************************************
Author        :supermaker
Created Time  :2015/12/15 23:38:23
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

int aa[maxn], out[maxn], sum[maxn<<2], n;

void PushUp (int rt)
{
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void Build (int rt, int l, int r)
{
	if (l == r)
	{
		sum[rt] = 1;
		return ;
	}
	int m = (l + r) >> 1;
	Build (lson);
	Build (rson);
	PushUp (rt);
}

int Query (int rt, int l, int r, int val)
{
	if (l == r) return l;

	int m = (l + r) >> 1;
	if (val <= sum[rt<<1]) return Query (lson, val);
	else return Query (rson, val - sum[rt<<1]);
}

void UpDate (int rt, int l, int r, int val)
{
	if (l == r)
	{
		sum[rt] = 0;
		return ; 
	}
	int m = (l + r) >> 1;
	if (val <= m) UpDate (lson, val);
	else UpDate (rson, val);
	PushUp (rt);
}

int main()
{
    //CFF;
    //CPPFF;
   	while (scanf ("%d", &n) != EOF)
	{
		for (int i = 2; i <= n; i++)
			scanf ("%d", &aa[i]);
		aa[1] = 0;
		
		Build (1, 1, n);
		for (int i = n; i >= 1; i--)
		{
			int tt = Query (1, 1, n, aa[i] + 1);
			out[i] = tt;
			UpDate (1, 1, n, tt);
		}

		for (int i = 1; i <= n; i++)
			printf ("%d\n", out[i]);
	}
    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

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

Author :supermaker

Created Time :2015/12/15 23:38:23

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

int aa[maxn], out[maxn], sum[maxn<<2], n;

void PushUp (int rt)

{

sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void Build (int rt, int l, int r)

{

if (l == r)

{

sum[rt] = 1;

return ;

}

int m = (l + r) >> 1;

Build (lson);

Build (rson);

PushUp (rt);

}

int Query (int rt, int l, int r, int val)

{

if (l == r) return l;

int m = (l + r) >> 1;

if (val <= sum[rt<<1]) return Query (lson, val);

else return Query (rson, val - sum[rt<<1]);

}

void UpDate (int rt, int l, int r, int val)

{

if (l == r)

{

sum[rt] = 0;

return ;

}

int m = (l + r) >> 1;

if (val <= m) UpDate (lson, val);

else UpDate (rson, val);

PushUp (rt);

}

int main()

{

//CFF;

//CPPFF;

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

{

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

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

aa[1] = 0;

Build (1, 1, n);

for (int i = n; i >= 1; i--)

{

int tt = Query (1, 1, n, aa[i] + 1);

out[i] = tt;

UpDate (1, 1, n, tt);

}

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

printf ("%d\n", out[i]);

}

return 0;

}

BestCoder Round #65 (4/5)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

06 12月 2015

A ZYB's Biology

Problem Description

After getting 600 scores in NOIP ZYB(ZJ-267) begins to work with biological questions.Now he give you a simple 阅读全文 »

Codeforces Round #334(Div.2) (3/5) (Div.1) (1/5)

maksyuki 发表于比赛分类，标签: 比赛-codeforces

06 12月 2015

A Uncowed Forces

Kevin Sun has just finished competing in Codeforces Round #334! The round was 120 minutes long and featured five problems with maximum point values of 500, 1000, 1500, 2000, and 2500, respectively. Despite the challenging tasks, Kevin was uncowed and bulldozed through all of them, distinguishing himself from the herd as the best cowmputer scientist in all of Bovinia. Kevin knows his submission time for each problem, the number of wrong submissions that he made on each problem, and his total numbers of successful and unsuccessful hacks. Because Codeforces scoring is complicated, Kevin wants you to write a program to compute his final score.

Codeforces scores are computed as follows: If the maximum point value of a problem is x, and Kevin submitted correctly at minute m but made w wrong submissions, then his score on that problem is . His total score is equal to the sum of his scores for each problem. In addition, Kevin's total score gets increased by 100 points for each successful hack, but gets decreased by 50 points for each unsuccessful hack.

All arithmetic operations are performed with absolute precision and no rounding. It is guaranteed that Kevin's final score is an integer.

Input

The first line of the input contains five space-separated integers m₁, m₂, m₃, m₄, m₅, where m_i (0 ≤ m_i ≤ 119) is the time of Kevin's last submission for problem i. His last submission is always correct and gets accepted.

The second line contains five space-separated integers w₁, w₂, w₃, w₄, w₅, where w_i (0 ≤ w_i ≤ 10) is Kevin's number of wrong submissions on problem i.

The last line contains two space-separated integers h_s and h_u (0 ≤ h_s, h_u ≤ 20), denoting the Kevin's numbers of successful and unsuccessful hacks, respectively.

Output

Print a single integer, the value of Kevin's final score.

Sample test(s)

input

20 40 60 80 100
0 1 2 3 4
1 0

output

4900

input

119 119 119 119 119
0 0 0 0 0
10 0

output

4930

Note

In the second sample, Kevin takes 119 minutes on all of the problems. Therefore, he gets of the points on each problem. So his score from solving problems is . Adding in 10·100 = 1000 points from hacks, his total score becomes 3930 + 1000 = 4930.

题目类型：水题

算法分析：直接按照题目模拟即可，注意0.3x在计算时需要用3 * x / 10来计算！！！

/*************************************************
Author        :supermaker
Created Time  :2015/12/16 23:22:28
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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;

const int cnt[] = {
	0, 500, 1000, 1500, 2000, 2500
};

int m[16], w[16];

int main()
{
    //CFF;
    //CPPFF;
	for (int i = 1; i <= 5; i++)
		scanf ("%d", &m[i]);

	for (int i = 1; i <= 5; i++)
		scanf ("%d", &w[i]);

	int h1, h2;
	scanf ("%d %d", &h1, &h2);

	int res = 0;
	for (int i = 1; i <= 5; i++)
	{
		int tt = max (3 * cnt[i] / 10, (250 - m[i]) * cnt[i] / 250 - 50 * w[i]);
		res += tt;
	}

	res += 100 * h1;
	res -= 50 * h2;
	printf ("%d\n", res);
    return 0;
}

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

Author :supermaker

Created Time :2015/12/16 23:22:28

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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;

const int cnt[] = {

0, 500, 1000, 1500, 2000, 2500

};

int m[16], w[16];

int main()

{

//CFF;

//CPPFF;

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

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

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

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

int h1, h2;

scanf ("%d %d", &h1, &h2);

int res = 0;

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

{

int tt = max (3 * cnt[i] / 10, (250 - m[i]) * cnt[i] / 250 - 50 * w[i]);

res += tt;

}

res += 100 * h1;

res -= 50 * h2;

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

return 0;

}

B More Cowbell

Kevin Sun wants to move his precious collection of n cowbells from Naperthrill to Exeter, where there is actually grass instead of corn. Before moving, he must pack his cowbells into k boxes of a fixed size. In order to keep his collection safe during transportation, he won't place more than two cowbells into a single box. Since Kevin wishes to minimize expenses, he is curious about the smallest size box he can use to pack his entire collection.

Kevin is a meticulous cowbell collector and knows that the size of his i-th (1 ≤ i ≤ n) cowbell is an integer s_i. In fact, he keeps his cowbells sorted by size, so s_i_- 1 ≤ s_i for any i > 1. Also an expert packer, Kevin can fit one or two cowbells into a box of size s if and only if the sum of their sizes does not exceed s. Given this information, help Kevin determine the smallest s for which it is possible to put all of his cowbells into k boxes of size s.

Input

The first line of the input contains two space-separated integers n and k (1 ≤ n ≤ 2·k ≤ 100 000), denoting the number of cowbells and the number of boxes, respectively.

The next line contains n space-separated integers s₁, s₂, ..., s_n (1 ≤ s₁ ≤ s₂ ≤ ... ≤ s_n ≤ 1 000 000), the sizes of Kevin's cowbells. It is guaranteed that the sizes s_i are given in non-decreasing order.

Output

Print a single integer, the smallest s for which it is possible for Kevin to put all of his cowbells into k boxes of size s.

Sample test(s)

input

2 1
2 5

output

input

4 3
2 3 5 9

output

input

3 2
3 5 7

output

Note

In the first sample, Kevin must pack his two cowbells into the same box.

In the second sample, Kevin can pack together the following sets of cowbells: {2, 3}, {5} and {9}.

In the third sample, the optimal solution is {3, 5} and {7}.

题目类型：简单贪心

算法分析：贪心策略是最大的值尽量要单独放，由题目可以算出有多少个箱子是只装一个物品的，然后对于装两个物品的箱子，每次枚举当前最小和当前最大的值并更新

/*************************************************
Author        :supermaker
Created Time  :2015/12/16 23:47:40
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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 aa[maxn], cnt[maxn];

int main()
{
    //CFF;
    //CPPFF;
	int n, k;
	scanf ("%d %d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf ("%d", &aa[i]);
   	int single = min (n, 2 * k - n);
	int pair = n - single;
	int res = aa[n];
	for (int i = 1, j = pair; i < j; i++, j--) 
		res = max (res, aa[i] + aa[j]);

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

	return 0;
}

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

Author :supermaker

Created Time :2015/12/16 23:47:40

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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 aa[maxn], cnt[maxn];

int main()

{

//CFF;

//CPPFF;

int n, k;

scanf ("%d %d", &n, &k);

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

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

int single = min (n, 2 * k - n);

int pair = n - single;

int res = aa[n];

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

res = max (res, aa[i] + aa[j]);

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

return 0;

}

C Alternative Thinking

Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. Each character of Kevin's string represents Kevin's score on one of the n questions of the olympiad—'1' for a correctly identified cow and '0' otherwise.

However, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define analternating subsequence of a string as a not-necessarily contiguous subsequence where no two consecutive elements are equal. For example, {0, 1, 0, 1}, {1, 0, 1}, and {1, 0, 1, 0} are alternating sequences, while{1, 0, 0} and {0, 1, 0, 1, 1} are not.

Kevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a contiguous non-empty substring of his score and change all '0's in that substring to '1's and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.

Input

The first line contains the number of questions on the olympiad n (1 ≤ n ≤ 100 000).

The following line contains a binary string of length n representing Kevin's results on the USAICO.

Output

Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.

Sample test(s)

input

8
10000011

output

input

2
01

output

Note

In the first sample, Kevin can flip the bolded substring '10000011' and turn his string into '10011011', which has an alternating subsequence of length 5: '10011011'.

In the second sample, Kevin can flip the entire string and still have the same score.

题目类型：构造

算法分析：将一个对任意区间的翻转行为看作是由两个前缀区间翻转得到的，而且相邻相同的值可以缩成一个值。这样一来易知若一个前缀区间最后一个值两边的值相同，则翻转这个区间会使得总个数+1，反之，则会使得总个数-1。简单化简并计算即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/20 23:23:31
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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 main()
{
    //CFF;
    //CPPFF;
	int n;
	cin >> n;
	string s;
	cin >> s;
	int res = 1;
	for (int i = 0; i < s.size () - 1; i++)
		if (s[i] != s[i+1])
			res++;
	cout << min (res + 2, n) << endl;
    return 0;
}

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

Author :supermaker

Created Time :2016/1/20 23:23:31

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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 main()

{

//CFF;

//CPPFF;

int n;

cin >> n;

string s;

cin >> s;

int res = 1;

for (int i = 0; i < s.size () - 1; i++)

if (s[i] != s[i+1])

res++;

cout << min (res + 2, n) << endl;

return 0;

}

codeforces 55D

maksyuki 发表于 oj 分类，标签: DP-数位DP

05 12月 2015

Beautiful numbers

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with 阅读全文 »

hdu4389

maksyuki 发表于 oj 分类，标签: DP-数位DP

05 12月 2015

X mod f(x)

Problem Description

Here is a function f(x): int f ( int x ) { if ( x == 0 ) return 0; return f ( x / 10 ) + x % 10;} Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 10⁹), how many integer x that mod f(x) equal to 0.

Input

The first line has an integer T (1 <= T <= 50), indicate the number of test cases.
Each test case has two integers A, B.

Output

For each test case, output only one line containing the case number and an integer indicated the number of x.

Sample Input

2
1 10
11 20

Sample Output

Case 1: 10

Case 2: 3

Author

WHU

Source

2012 Multi-University Training Contest 9

题目类型：数位DP

算法分析：dp[pos][mod][d][sum]表示前i位数除以d得到余数mod且此时前i位和为sum的数字的个数，这里d在1~81范围内枚举，递归的边界是恰好满足d == sum且mod % sum == 0，最后累加所有的情况即可(枚举d)

/*************************************************
Author        :supermaker
Created Time  :2015/12/4 23:45:43
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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[12][83][83][83], bit[66];

int SS (int pos, int mod, int d, int sum, bool flag)
{
	if (pos == 0) return (d == sum && mod % sum == 0);
	if (flag && dp[pos][mod][d][sum] != -1) return dp[pos][mod][d][sum];
	
	int res = 0;
	int x = flag ? 9 : bit[pos];
	for (int i = 0; i <= x; i++)
	{
		int tt = (mod * 10 + i) % d;
		res += SS (pos - 1, tt, d, sum + i, flag || i < x);
	}
	return flag ? dp[pos][mod][d][sum] = res : res;
}

int Calc (int val)
{
	int len = 0;
	while (val)
	{
		bit[++len] = val % 10;
		val /= 10;
	}
	
	int res = 0;
	for (int i = 1; i <= 81; i++)
		res += SS (len, 0, i, 0, 0);
	return res;
}

int main()
{
    //CFF;
    //CPPFF;
	memset (dp, -1, sizeof (dp));
	int t, id = 1;
	scanf ("%d", &t);
	while (t--)
	{
		int vala, valb;
		scanf ("%d%d", &vala, &valb);
		printf ("Case %d: %d\n", id++, Calc (valb) - Calc (vala - 1));
	}
    return 0;
}

100

101

102

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

Author :supermaker

Created Time :2015/12/4 23:45:43

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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[12][83][83][83], bit[66];

int SS (int pos, int mod, int d, int sum, bool flag)

{

if (pos == 0) return (d == sum && mod % sum == 0);

if (flag && dp[pos][mod][d][sum] != -1) return dp[pos][mod][d][sum];

int res = 0;

int x = flag ? 9 : bit[pos];

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

{

int tt = (mod * 10 + i) % d;

res += SS (pos - 1, tt, d, sum + i, flag || i < x);

}

return flag ? dp[pos][mod][d][sum] = res : res;

}

int Calc (int val)

{

int len = 0;

while (val)

{

bit[++len] = val % 10;

val /= 10;

}

int res = 0;

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

res += SS (len, 0, i, 0, 0);

return res;

}

int main()

{

//CFF;

//CPPFF;

memset (dp, -1, sizeof (dp));

int t, id = 1;

scanf ("%d", &t);

while (t--)

{

int vala, valb;

scanf ("%d%d", &vala, &valb);

printf ("Case %d: %d\n", id++, Calc (valb) - Calc (vala - 1));

}

return 0;

}

hdu3652

maksyuki 发表于 oj 分类，标签: DP-数位DP

04 12月 2015

B-number

Problem Description

A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.

Input

Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).

Output

Print each answer in a single line.

Sample Input

13
100
200
1000

Sample Output

Author

wqb0039

Source

2010 Asia Regional Chengdu Site —— Online Contest

题目类型：数位DP

算法分析：dp[i][j][k]表示满足状态为k，且模上13后值为j的i位数个数，类似于HDU3555，只不过是在递归边界上还要额外满足j == 0，在每次向低位搜索时都要计算模值：mod = (mod * 10 + i) % 13

/*************************************************
Author        :supermaker
Created Time  :2015/12/4 23:03:38
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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;

LL dp[166][16][3], bit[166];

LL SS (int pos, int mod, int st, bool flag)
{
	if (pos == 0) return (st == 2 && mod == 0); 
	if (flag && dp[pos][mod][st] != -1) return dp[pos][mod][st];

	LL res = 0;
	int x = flag ? 9 : bit[pos];
	for (int i = 0; i <= x; i++)
	{
		int tt = (mod * 10 + i) % 13;
		if ((st == 2) || (st == 1 && i == 3)) res += SS (pos - 1, tt, 2, flag || i < x);
		else if (i == 1) res += SS (pos - 1, tt, 1, flag || i < x);
		else res += SS (pos - 1, tt, 0, flag || i < x);
	}

	return flag ? dp[pos][mod][st] = res : res;
}

LL Calc (LL val)
{
	memset (dp, -1, sizeof (dp));
	int len = 0;
	while (val)
	{
		bit[++len] = val % 10;
		val /= 10;
	}
	return SS (len, 0, 0, 0);
}

int main()
{
    //CFF;
    //CPPFF;
	LL n;
	while (scanf ("%I64d", &n) != EOF)
	{
		printf ("%I64d\n", Calc (n));
	}
    return 0;
}

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

Author :supermaker

Created Time :2015/12/4 23:03:38

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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;

LL dp[166][16][3], bit[166];

LL SS (int pos, int mod, int st, bool flag)

{

if (pos == 0) return (st == 2 && mod == 0);

if (flag && dp[pos][mod][st] != -1) return dp[pos][mod][st];

LL res = 0;

int x = flag ? 9 : bit[pos];

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

{

int tt = (mod * 10 + i) % 13;

if ((st == 2) || (st == 1 && i == 3)) res += SS (pos - 1, tt, 2, flag || i < x);

else if (i == 1) res += SS (pos - 1, tt, 1, flag || i < x);

else res += SS (pos - 1, tt, 0, flag || i < x);

}

return flag ? dp[pos][mod][st] = res : res;

}

LL Calc (LL val)

{

memset (dp, -1, sizeof (dp));

int len = 0;

while (val)

{

bit[++len] = val % 10;

val /= 10;

}

return SS (len, 0, 0, 0);

}

int main()

{

//CFF;

//CPPFF;

LL n;

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

{

printf ("%I64d\n", Calc (n));

}

return 0;

}

hdu2639

maksyuki 发表于 oj 分类，标签: DP-背包

03 12月 2015

Bone Collector II

Problem Description

The title of this problem is familiar,isn't it?yeah,if you had took part in the "Rookie Cup" competition,you must have seem this title.If you haven't seen it before,it doesn't matter,I will give you a link:

Here is the link:http://acm.hdu.edu.cn/showproblem.php?pid=2602

Today we are not desiring the maximum value of bones,but the K-th maximum value of the bones.NOTICE that,we considerate two ways that get the same value of bones are the same.That means,it will be a strictly decreasing sequence from the 1st maximum , 2nd maximum .. to the K-th maximum.

If the total number of different values is less than K,just ouput 0.

Input

The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, K(N <= 100 , V <= 1000 , K <= 30)representing the number of bones and the volume of his bag and the K we need. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the K-th maximum of the total value (this number will be less than 2³¹).

Sample Input

3
5 10 2
1 2 3 4 5
5 4 3 2 1
5 10 12
1 2 3 4 5
5 4 3 2 1
5 10 16
1 2 3 4 5
5 4 3 2 1

Sample Output

Author

teddy

Source

百万秦关终属楚

题目类型：01背包第k优解

算法分析：dp[i][j]表示恰好填满体积为i的背包的第j优解(value)，每次递推的时候把两个状态的前i个最优解合并起来即可，最后输出dp[V][K]

/*************************************************
Author        :supermaker
Created Time  :2015/12/3 14:36:11
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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[1666][36], c[1666], w[1666], ta[36], tb[36], N, V, K;

void Kth_ZeroOnePack (int c, int w)
{
	for (int i = V; i >= c; i--)
	{
		for (int k = 1; k <= K; k++)
		{
			ta[k] = dp[i][k];
			tb[k] = dp[i-c][k] + w;
		}
		
		ta[K+1] = tb[K+1] = -1;
		for (int j = 1, k = 1, q = 1; j <= K && (ta[k] != -1 || tb[q] != -1); )
		{
			if (ta[k] >= tb[q]) dp[i][j] = ta[k++];
			else dp[i][j] = tb[q++];
			if (dp[i][j] != dp[i][j-1]) j++;
		}
	}
}

int main()
{
    //CFF;
    //CPPFF;
	int t;
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d%d%d", &N, &V, &K);
		for (int i = 1; i <= N; i++)
			scanf ("%d", &w[i]);

		for (int i = 1; i <= N; i++)
			scanf ("%d", &c[i]);
		
		memset (dp, 0, sizeof (dp));
		for (int i = 1; i <= N; i++)
				Kth_ZeroOnePack (c[i], w[i]);

		printf ("%d\n", dp[V][K]);
	}
    return 0;
}

100

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

Author :supermaker

Created Time :2015/12/3 14:36:11

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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[1666][36], c[1666], w[1666], ta[36], tb[36], N, V, K;

void Kth_ZeroOnePack (int c, int w)

{

for (int i = V; i >= c; i--)

{

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

{

ta[k] = dp[i][k];

tb[k] = dp[i-c][k] + w;

}

ta[K+1] = tb[K+1] = -1;

for (int j = 1, k = 1, q = 1; j <= K && (ta[k] != -1 || tb[q] != -1); )

{

if (ta[k] >= tb[q]) dp[i][j] = ta[k++];

else dp[i][j] = tb[q++];

if (dp[i][j] != dp[i][j-1]) j++;

}

int main()

{

//CFF;

//CPPFF;

int t;

scanf ("%d", &t);

while (t--)

{

scanf ("%d%d%d", &N, &V, &K);

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

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

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

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

memset (dp, 0, sizeof (dp));

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

Kth_ZeroOnePack (c[i], w[i]);

printf ("%d\n", dp[V][K]);

}

return 0;

}

hdu5115

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

03 12月 2015

Dire Wolf

Problem Description

Dire wolves, also known as Dark wolves, are extraordinarily large and powerful wolves. Many, if not all, 阅读全文 »

hdu1078

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

02 12月 2015

FatMouse and Cheese

Problem Description

FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he's going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse -- after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.

Input

There are several test cases. Each test case consists of

a line containing two integers between 1 and 100: n and k
n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) ... (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), ... (1,n-1), and so on.
The input ends with a pair of -1's.

Output

For each test case output in a line the single integer giving the number of blocks of cheese collected.

Sample Input

3 1
1 2 5
10 11 6
12 12 7
-1 -1

Sample Output

Source

Zhejiang University Training Contest 2001

题目类型：线性DP(记忆化搜索)

算法分析：dp[i][j]表示(i, j)位置所最终能够得到的最大的奶酪数，则状态转移方程为dp[i][j] = max (dp[k][q]) + aa[i][j]，其中aa[k][q] < aa[i][j]，而(k, q)合理且由(i,j)经过不超过k步转移过来，最后直接找dp[i][j]的最大值即可

/*************************************************
Author        :supermaker
Created Time  :2015/12/2 21:58:21
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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;

LL dp[166][166], aa[166][166], n, k;

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

bool In (int x, int y)
{
	if (x >= 1 && x <= n && y >= 1 && y <= n) return true;
	return false;
}

LL dfs (int x, int y)
{
	LL res = 0;
	if (dp[x][y]) return dp[x][y];
	for (int i = 1; i <= k; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			int tx = x + i * dx[j], ty = y + i * dy[j];
			if (In (tx, ty) && aa[tx][ty] > aa[x][y])
				res = max (res, dfs (tx, ty));
		}
	}
	return dp[x][y] = res + aa[x][y];
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%lld%lld", &n, &k) != EOF)
	{
		if (n == -1 && k == -1)
			break;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				scanf ("%lld", &aa[i][j]);
		
		memset (dp, 0, sizeof (dp));
		dfs (1, 1);

		LL maxval = -INF;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				maxval = max (maxval, dp[i][j]);

		printf ("%lld\n", maxval);
	}
    return 0;
}

100

101

102

103

104

105

106

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

Author :supermaker

Created Time :2015/12/2 21:58:21

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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;

LL dp[166][166], aa[166][166], n, k;

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

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

bool In (int x, int y)

{

if (x >= 1 && x <= n && y >= 1 && y <= n) return true;

return false;

}

LL dfs (int x, int y)

{

LL res = 0;

if (dp[x][y]) return dp[x][y];

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

{

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

{

int tx = x + i * dx[j], ty = y + i * dy[j];

if (In (tx, ty) && aa[tx][ty] > aa[x][y])

res = max (res, dfs (tx, ty));

}

return dp[x][y] = res + aa[x][y];

}

int main()

{

//CFF;

//CPPFF;

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

{

if (n == -1 && k == -1)

break;

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

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

scanf ("%lld", &aa[i][j]);

memset (dp, 0, sizeof (dp));

dfs (1, 1);

LL maxval = -INF;

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

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

maxval = max (maxval, dp[i][j]);

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

}

return 0;

}

poj3616

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

02 12月 2015

Milking Time

Bessie is such a hard-working cow. In fact, she is so focused on maximizing her productivity that she decides to schedule her next N (1 ≤ N ≤ 1,000,000) hours (conveniently labeled 0..N-1) so that she produces as much milk as possible.

Farmer John has a list of M (1 ≤ M ≤ 1,000) possibly overlapping intervals in which he is available for milking. Each interval i has a starting hour (0 ≤ starting_hour_i ≤ N), an ending hour (starting_hour_i < ending_hour_i ≤ N), and a corresponding efficiency (1 ≤ efficiency_i ≤ 1,000,000) which indicates how many gallons of milk that he can get out of Bessie in that interval. Farmer John starts and stops milking at the beginning of the starting hour and ending hour, respectively. When being milked, Bessie must be milked through an entire interval.

Even Bessie has her limitations, though. After being milked during any interval, she must rest R (1 ≤ R ≤ N) hours before she can start milking again. Given Farmer Johns list of intervals, determine the maximum amount of milk that Bessie can produce in the N hours.

Input

* Line 1: Three space-separated integers: N, M, and R
* Lines 2..M+1: Line i+1 describes FJ's ith milking interval withthree space-separated integers: starting_hour_i , ending_hour_i , and efficiency_i

Output

* Line 1: The maximum number of gallons of milk that Bessie can product in the N hours

Sample Input

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

Sample Output

Source

USACO 2007 November Silver

题目类型：线性DP

算法分析：dp[i]表示以第i个时间段为结尾所能够挤出的最大奶量，类似最长递增子序列的递推形式

/*************************************************
Author        :supermaker
Created Time  :2015/12/2 14:38:24
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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 = 1e6 + 666;

LL dp[maxn];

struct node
{
	LL a, b, c;
};

bool operator < (const node&va, const node&vb) {
	if (va.a != vb.a) return va.a < vb.a;
	return va.b < vb.b;
}

node aa[maxn];

int main()
{
    //CFF;
    //CPPFF;
	int N, M, R;
	while (scanf ("%d%d%d", &N, &M, &R) != EOF)
	{
		for (int i = 1; i <= M; i++)
			scanf("%lld%lld%lld", &aa[i].a, &aa[i].b, &aa[i].c);
			
		sort (aa + 1, aa + 1 + M);
		dp[1] = aa[1].c;
		for (int i = 2; i <= M; i++)
		{
			LL maxvala = 0;
			for (int j = 1; j <= i - 1; j++)
				if (aa[j].b + R <= aa[i].a)
					maxvala = max (maxvala, dp[j]);
			dp[i] = maxvala + aa[i].c;
		}

		printf ("%lld\n", *max_element (dp + 1, dp + 1 + M));
	}
    return 0;
}

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

Author :supermaker

Created Time :2015/12/2 14:38:24

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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 = 1e6 + 666;

LL dp[maxn];

struct node

{

LL a, b, c;

};

bool operator < (const node&va, const node&vb) {

if (va.a != vb.a) return va.a < vb.a;

return va.b < vb.b;

}

node aa[maxn];

int main()

{

//CFF;

//CPPFF;

int N, M, R;

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

{

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

scanf("%lld%lld%lld", &aa[i].a, &aa[i].b, &aa[i].c);

sort (aa + 1, aa + 1 + M);

dp[1] = aa[1].c;

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

{

LL maxvala = 0;

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

if (aa[j].b + R <= aa[i].a)

maxvala = max (maxvala, dp[j]);

dp[i] = maxvala + aa[i].c;

}

printf ("%lld\n", *max_element (dp + 1, dp + 1 + M));

}

return 0;

}

poj3186

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

02 12月 2015

Treats for the Cows

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time.

The treats are interesting for many reasons:

The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats.
Like fine wines and delicious cheeses, the treats improve with age and command greater prices.
The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000).
Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a.

Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally?

The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains the value of treat v(i)

Output

Line 1: The maximum revenue FJ can achieve by selling the treats

Sample Input

Sample Output

Hint

Explanation of the sample:

Five treats. On the first day FJ can sell either treat #1 (value 1) or treat #5 (value 2).

FJ sells the treats (values 1, 3, 1, 5, 2) in the following order of indices: 1, 5, 2, 3, 4, making 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

Source

USACO 2006 February Gold & Silver

题目类型：区间DP

算法分析：dp[i][j]表示[i,j]范围内的子序列所能够到达的最大值，则状态转移方程为dp[i][j] = max (dp[i+1][j] + aa[i] * (n - len), dp[i][j-1] + aa[j] * (n - len))，初始化dp[i][i] = aa[i] * n，最后直接输出dp[1][n]即可

/*************************************************
Author        :supermaker
Created Time  :2015/12/2 14:05:29
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 ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#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[2666][2666], aa[maxn];


int main()
{
   	//CFF;
    //CPPFF;
	int n;
	while (scanf ("%d", &n) != EOF)
	{
		memset (dp, 0, sizeof (dp));
		for (int i = 1; i <= n; i++)
		{
			scanf ("%d", &aa[i]);
			dp[i][i] = aa[i] * n;
		}

		for (int len = 1; len <= n; len++)
			for (int i = 1; i + len <= n; i++)
			{
				int j = i + len;
				dp[i][j] = max (dp[i+1][j] + aa[i] * (n - len), dp[i][j-1] + aa[j] * (n - len));
			}

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

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

Author :supermaker

Created Time :2015/12/2 14:05:29

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 ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#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[2666][2666], aa[maxn];

int main()

{

//CFF;

//CPPFF;

int n;

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

{

memset (dp, 0, sizeof (dp));

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

{

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

dp[i][i] = aa[i] * n;

}

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

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

{

int j = i + len;

dp[i][j] = max (dp[i+1][j] + aa[i] * (n - len), dp[i][j-1] + aa[j] * (n - len));

}

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

}

return 0;

}

hdu2089

maksyuki 发表于 oj 分类，标签: DP-数位DP

01 12月 2015

不要62

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样阅读全文 »

超客的水墨烟雨

BestCoder Round #67 (2/4)

A N bulbs

Codeforces Round #336(Div.2) (1/5) (Div.1) (0/5)

TopCoder SRM#676(Div2)(2/3)

poj2182

BestCoder Round #65 (4/5)

A ZYB's Biology

Codeforces Round #334(Div.2) (3/5) (Div.1) (1/5)

codeforces 55D

hdu4389

X mod f(x)

hdu3652

B-number

hdu2639

Bone Collector II

hdu5115

Dire Wolf

hdu1078

FatMouse and Cheese

poj3616

poj3186

hdu2089

不要62

分类目录

标签云

书签

近期评论

2015年12月
一	二	三	四	五	六	日
« 11月				1月 »
	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