11 | 2月 | 2017 | 超客的水墨烟雨

poj3666

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

11 2月 2017

Making the Grade

A straight dirt road connects two fields on FJ's farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down).

You are given N integers A₁, ... , A_N (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ A_i ≤ 1,000,000,000) at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence B₁, . ... , B_N that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is

|A₁- B₁| + |A₂- B₂| + ... + |A_N - B_N |

Please compute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer.

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer elevation: A_i

Output

* Line 1: A single integer that is the minimum cost for FJ to grade his dirt road so it becomes nonincreasing or nondecreasing in elevation.

Sample Input

Sample Output

Source

USACO 2008 February Gold

题目类型：线性DP

算法分析：dp[i][j]表示前i个数字且最后数字是第j小的最小改动量，这里有一个贪心思想是一个数字改动成相邻两个数字的值的时候才能构成最小改动量。初始化dp[1][0] = a[1] - b[i]，其中在非递减序列中b[i]为a[i]递增排序后的值，状态转移方程为dp[i][j] = min(dp[i-1][k]) + abs(a[i] - b[j]) k=1->j，由于min(dp[i-1][k]) = min(dp[i-1][1], dp[i-1][2], … dp[i-1][j])，而dp[i-1][1]当i==2时是已知的，所以可以利用前缀性质优化求解k所在的循环，最后循环更新最大值即可

/**************************************************
filename       :e.cpp
author         :maksyuki
created time   :2017/2/11 18:50:59
last modified  :2017/2/11 19:09:44
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 a[2000+6], b[2000+6];
int dp[2][2000+6];

int main()
{
    //CFF;
    //CPPFF;
    int n;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        
        sort(b + 1, b + 1 + n);
        for(int i = 1; i <= n; i++)
            dp[1&1][i] = abs(a[1] - b[i]);

        for(int i = 2; i <= n; i++)
        {
            int minval = INF;
            for(int j = 1; j <= n; j++)
            {
                minval = min(minval, dp[(i-1)&1][j]);
                dp[i&1][j] = minval + abs(a[i] - b[j]);
            }
        }

        int res = INF;
        for(int i = 1; i <= n; i++)
            res = min(res, dp[n&1][i]);
        
        sort(b + 1, b + 1 + n, greater<int>());
        for(int i = 1; i <= n; i++)
            dp[1&1][i] = abs(a[1] - b[i]);

        for(int i = 2; i <= n; i++)
        {
            int minval = INF;
            for(int j = 1; j <= n; j++)
            {
                minval = min(minval, dp[(i-1)&1][j]);
                dp[i&1][j] = minval + abs(a[i] - b[j]);
            }
        }

        for(int i = 1; i <= n; i++)
            res = min(res, dp[n&1][i]);

        printf("%d\n", res);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

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

filename :e.cpp

author :maksyuki

created time :2017/2/11 18:50:59

last modified :2017/2/11 19:09:44

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 a[2000+6], b[2000+6];

int dp[2][2000+6];

int main()

{

//CFF;

//CPPFF;

int n;

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

{

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

{

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

b[i] = a[i];

}

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

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

dp[1&1][i] = abs(a[1] - b[i]);

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

{

int minval = INF;

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

{

minval = min(minval, dp[(i-1)&1][j]);

dp[i&1][j] = minval + abs(a[i] - b[j]);

}

int res = INF;

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

res = min(res, dp[n&1][i]);

sort(b + 1, b + 1 + n, greater<int>());

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

dp[1&1][i] = abs(a[1] - b[i]);

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

{

int minval = INF;

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

{

minval = min(minval, dp[(i-1)&1][j]);

dp[i&1][j] = minval + abs(a[i] - b[j]);

}

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

res = min(res, dp[n&1][i]);

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

}

return 0;

}

poj1548

maksyuki 发表于 oj 分类，标签: DP-线性DP, 组合数学-Dilworth定理

11 2月 2017

Robots

Your company provides robots that can be used to pick up litter from fields after sporting events and concerts. Before robots are assigned to a job, an aerial photograph of the field is marked with a grid. Each location in the grid that contains garbage is marked. All robots begin in the Northwest corner and end their movement in the Southeast corner. A robot can only move in two directions, either to the East or South. Upon entering a cell that contains garbage, the robot will pick it up before proceeding. Once a robot reaches its destination at the Southeast corner it cannot be repositioned or reused. Since your expenses are directly proportional to the number of robots used for a particular job, you are interested in finding the minimum number of robots that can clean a given field. For example, consider the field map shown in Figure 1 with rows and columns numbered as shown and garbage locations marked with a 'G'. In this scheme, all robots will begin in location 1,1 and end in location 6, 7.
Figure 1 - A Field Map
Figure 2 below shows two possible solutions, the second of which is preferable since it uses two robots rather than three.
Figure 2 - Two Possible Solutions
Your task is to create a program that will determine the minimum number of robots needed to pick up all the garbage from a field.

Input

The input consists of one or more field maps followed by a line containing -1 -1 to signal the end of the input data. A field map consists of one or more lines, each containing one garbage location, followed by a line containing 0 0 to signal the end of the map. Each garbage location consists of two integers, the row and column, separated by a single space. The rows and columns are numbered as shown in Figure 1. The garbage locations will be given in row-major order. No single field map will have more than 24 rows and 24 columns. The sample input below shows an input file with two field maps. The first is the field map from Figure 1.

Output

The output will consist of a single line for each field map containing the minimum number of robots needed to clean the corresponding field.

Sample Input

1 2
1 4
2 4
2 6
4 4
4 7
6 6
0 0
1 1
2 2
4 4
0 0
-1 -1

Sample Output

Source

Mid-Central USA 2003

题目类型：最长下降子序列

算法分析：详细参考http://www.hankcs.com/program/cpp/poj-1065-wooden-sticks.html和http://blog.csdn.net/vmurder/article/detail/40818831

/**************************************************
filename       :d.cpp
author         :maksyuki
created time   :2017/2/11 9:35:11
last modified  :2017/2/11 9:41:22
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;

struct point
{
    int x, y;
};

bool cmp(const point &a, const point &b)
{
    return a.x < b.x;
}

point a[66*66];
int dp[66*66];

int main()
{
    //CFF;
    //CPPFF;
    int tmpx, tmpy;
    while(scanf("%d%d", &tmpx, &tmpy) != EOF)
    {
        if(tmpx == -1 && tmpy == -1)
            break;

        int len = 0;
        do
        {
            if(!tmpx && !tmpy) break;
            a[len].x = tmpx, a[len].y = tmpy;
            len++;
        }while(scanf("%d%d", &tmpx, &tmpy));

        sort(a, a + len, cmp);
        for(int i = 0; i < len; i++)
            dp[i] = 1;
        
        for(int i = 0; i < len; i++)
            for(int j = 0; j < i; j++)
                if(a[i].y < a[j].y)
                    dp[i] = max(dp[i], dp[j] + 1);

        int res = -INF;
        for(int i = 0; i < len; i++)
            res = max(res, dp[i]);
        printf("%d\n", res);
    }
    return 0;
}

100

101

102

103

104

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

filename :d.cpp

author :maksyuki

created time :2017/2/11 9:35:11

last modified :2017/2/11 9:41:22

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;

struct point

{

int x, y;

};

bool cmp(const point &a, const point &b)

{

return a.x < b.x;

}

point a[66*66];

int dp[66*66];

int main()

{

//CFF;

//CPPFF;

int tmpx, tmpy;

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

{

if(tmpx == -1 && tmpy == -1)

break;

int len = 0;

{

if(!tmpx && !tmpy) break;

a[len].x = tmpx, a[len].y = tmpy;

len++;

}while(scanf("%d%d", &tmpx, &tmpy));

sort(a, a + len, cmp);

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

dp[i] = 1;

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

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

if(a[i].y < a[j].y)

dp[i] = max(dp[i], dp[j] + 1);

int res = -INF;

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

res = max(res, dp[i]);

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

}

return 0;

}

poj1065

maksyuki 发表于 oj 分类，标签: DP-线性DP, 组合数学-Dilworth定理

11 2月 2017

Wooden Sticks

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l <= l' and w <= w'. Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1 <= n <= 5000 , that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l1 , w1 , l2 , w2 ,..., ln , wn , each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

Output

The output should contain the minimum setup time in minutes, one per line.

Sample Input

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

Sample Output

Source

Taejon 2001

题目类型：最长下降子序列

算法分析：详细参考http://www.hankcs.com/program/cpp/poj-1065-wooden-sticks.html和http://blog.csdn.net/vmurder/article/details/40818831和http://www.cnblogs.com/fstang/archive/2013/03/31/2991255.html

/**************************************************
filename       :c.cpp
author         :maksyuki
created time   :2017/2/11 8:53:13
last modified  :2017/2/11 9:03: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 ("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;

struct point
{
    int l, w;
};

bool cmp(const point &a, const point &b)
{
    return a.l < b.l;
}

point a[5000+666];
int dp[5000+666];

int main()
{
    //CFF;
    //CPPFF;
    int t;
    scanf("%d", &t);

    while(t--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d%d", &a[i].l, &a[i].w);
        
        sort(a + 1, a + 1 + n, cmp);
        for(int i = 1; i <= n; i++)
            dp[i] = 1;

        for(int i = 1; i <= n; i++)
            for(int j = 1; j < i; j++)
                if(a[i].w < a[j].w)
                    dp[i] = max(dp[i], dp[j] + 1);

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

100

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

filename :c.cpp

author :maksyuki

created time :2017/2/11 8:53:13

last modified :2017/2/11 9:03: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 ("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;

struct point

{

int l, w;

};

bool cmp(const point &a, const point &b)

{

return a.l < b.l;

}

point a[5000+666];

int dp[5000+666];

int main()

{

//CFF;

//CPPFF;

int t;

scanf("%d", &t);

while(t--)

{

int n;

scanf("%d", &n);

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

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

sort(a + 1, a + 1 + n, cmp);

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

dp[i] = 1;

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

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

if(a[i].w < a[j].w)

dp[i] = max(dp[i], dp[j] + 1);

int res = -INF;

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

res = max(res, dp[i]);

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

}

return 0;

}

超客的水墨烟雨

poj3666

poj1548

poj1065

分类目录

标签云

书签

近期评论

2017年2月
一	二	三	四	五	六	日
« 4月				3月 »
		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