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

poj1018

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

14 2月 2017

Communication System

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Output

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

Sample Input

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

Sample Output

0.649

Source

Tehran 2002, First Iran Nationwide Internet Programming Contest

题目类型：线性DP

算法分析：dp[i][j]表示选择前i种服务带宽为j的最小费用，初始化dp[i][j] = INF，状态转移方程为dp[i][min(b[i][j],k)] = min(dp[i][min(b[i][j],k)], dp[i-1][k] + p[i][j])，最后枚举更新i / dp[n][i]的最大值即可

/**************************************************
filename       :f.cpp
author         :maksyuki
created time   :2017/2/14 21:00:49
last modified  :2017/2/14 21:21:49
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

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

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

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

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

int b[maxn][maxn], p[maxn][maxn], dp[maxn][maxn*maxn];

int main()
{
    //CFF;
    //CPPFF;
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        int maxb = -INF;
        for(int i = 1; i <= n; i++)
        {
            int mi;
            scanf("%d", &mi);
            for(int j = 1; j <= mi; j++)
            {
                scanf("%d%d", &b[i][j], &p[i][j]);
                maxb = max(maxb, b[i][j]); 
            }
            b[i][0] = mi;
        }

        for(int i = 0; i < maxn; i++)
            for(int j = 0; j < maxn * maxn; j++)
                dp[i][j] = INF;

        for(int i = 1; i <= b[1][0]; i++)
            dp[1][b[1][i]] = min(dp[1][b[1][i]], p[1][i]);

        for(int i = 2; i <= n; i++)
            for(int j = 1; j <= b[i][0]; j++)
                for(int k = 0; k <= maxb; k++)
                    if(dp[i-1][k] < INF)
                        dp[i][min(b[i][j],k)] = min(dp[i][min(b[i][j],k)], dp[i-1][k] + p[i][j]);

        double res = -INF;
        for(int i = 0; i <= maxb; i++)
            if(dp[n][i] < INF)
                res = max(res, i / 1.0 / dp[n][i]);

        printf("%.3lf\n", res);
    }
    return 0;
}

100

101

102

103

104

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

filename :f.cpp

author :maksyuki

created time :2017/2/14 21:00:49

last modified :2017/2/14 21:21:49

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

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

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

#define CPPFF ifstream cin ("in")

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

#define PB push_back

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

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100 + 2;

int b[maxn][maxn], p[maxn][maxn], dp[maxn][maxn*maxn];

int main()

{

//CFF;

//CPPFF;

int t;

scanf("%d", &t);

while(t--)

{

int n;

scanf("%d", &n);

int maxb = -INF;

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

{

int mi;

scanf("%d", &mi);

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

{

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

maxb = max(maxb, b[i][j]);

}

b[i][0] = mi;

}

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

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

dp[i][j] = INF;

for(int i = 1; i <= b[1][0]; i++)

dp[1][b[1][i]] = min(dp[1][b[1][i]], p[1][i]);

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

for(int j = 1; j <= b[i][0]; j++)

for(int k = 0; k <= maxb; k++)

if(dp[i-1][k] < INF)

dp[i][min(b[i][j],k)] = min(dp[i][min(b[i][j],k)], dp[i-1][k] + p[i][j]);

double res = -INF;

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

if(dp[n][i] < INF)

res = max(res, i / 1.0 / dp[n][i]);

printf("%.3lf\n", res);

}

return 0;

}

poj2686

maksyuki 发表于 oj 分类，标签: DP-状压DP

13 2月 2017

Traveling by Stagecoach

Once upon a time, there was a traveler.

He plans to travel using stagecoaches (horse wagons). His starting point and destination are fixed, but he cannot determine his route. Your job in this problem is to write a program which determines the route for him.

There are several cities in the country, and a road network connecting them. If there is a road between two cities, one can travel by a stagecoach from one of them to the other. A coach ticket is needed for a coach ride. The number of horses is specified in each of the tickets. Of course, with more horses, the coach runs faster.

At the starting point, the traveler has a number of coach tickets. By considering these tickets and the information on the road network, you should find the best possible route that takes him to the destination in the shortest time. The usage of coach tickets should be taken into account.

The following conditions are assumed.

A coach ride takes the traveler from one city to another directly connected by a road. In other words, on each arrival to a city, he must change the coach.
Only one ticket can be used for a coach ride between two cities directly connected by a road.
Each ticket can be used only once.
The time needed for a coach ride is the distance between two cities divided by the number of horses.
The time needed for the coach change should be ignored.

Input

The input consists of multiple datasets, each in the following format. The last dataset is followed by a line containing five zeros (separated by a space).

n m p a b
t1 t2 ... tn
x1 y1 z1
x2 y2 z2
...
xp yp zp

Every input item in a dataset is a non-negative integer. If a line contains two or more input items, they are separated by a space.

n is the number of coach tickets. You can assume that the number of tickets is between 1 and 8. m is the number of cities in the network. You can assume that the number of cities is between 2 and 30. p is the number of roads between cities, which may be zero.

a is the city index of the starting city. b is the city index of the destination city. a is not equal to b. You can assume that all city indices in a dataset (including the above two) are between 1 and m.

The second line of a dataset gives the details of coach tickets. ti is the number of horses specified in the i-th coach ticket (1<=i<=n). You can assume that the number of horses is between 1 and 10.

The following p lines give the details of roads between cities. The i-th road connects two cities with city indices xi and yi, and has a distance zi (1<=i<=p). You can assume that the distance is between 1 and 100.

No two roads connect the same pair of cities. A road never connects a city with itself. Each road can be traveled in both directions.

Output

For each dataset in the input, one line should be output as specified below. An output line should not contain extra characters such as spaces.

If the traveler can reach the destination, the time needed for the best route (a route with the shortest time) should be printed. The answer should not have an error greater than 0.001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.

If the traveler cannot reach the destination, the string "Impossible" should be printed. One cannot reach the destination either when there are no routes leading to the destination, or when the number of tickets is not sufficient. Note that the first letter of "Impossible" is in uppercase, while the other letters are in lowercase.

Sample Input

3 4 3 1 4
3 1 2
1 2 10
2 3 30
3 4 20
2 4 4 2 1
3 1
2 3 3
1 3 3
4 1 2
4 2 5
2 4 3 4 1
5 5
1 2 10
2 3 10
3 4 10
1 2 0 1 2
1
8 5 10 1 5
2 7 1 8 4 5 6 3
1 2 5
2 3 4
3 4 7
4 5 3
1 3 25
2 4 23
3 5 22
1 4 45
2 5 51
1 5 99
0 0 0 0 0

Sample Output

30.000
3.667
Impossible
Impossible
2.856

Hint

Since the number of digits after the decimal point is not specified, the above result is not the only solution. For example, the following result is also acceptable.

30.0
3.66667
Impossible
Impossible
2.85595

Source

Japan 2005 Domestic

题目类型：状态压缩DP

算法分析：dp[i][j]表示在顶点j处未使用票的集合为i时的从起点到j的最小花费，初始化dp数组为INF，dp[(1<<n)-1][a] = 0，状态转移方程为dp[s&(~(1<<i))][v] = min(dp[s&(~(1<<i))][v], dp[u][v] + (double)edge[u][v] / t[i])，最后使用dp[s][b]更新最大值即可

/**************************************************
filename       :c.cpp
author         :maksyuki
created time   :2017/2/13 8:56:23
last modified  :2017/2/13 9:39:35
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 = 30 + 66;

int t[8+66], edge[maxn][maxn];
double dp[1<<9][maxn];

int main()
{
    //CFF;
    //CPPFF;
    int n, m, p, a, b;
    while(scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) != EOF)
    {
        if(!n && !m && !p && !a && !b)
            break;

        for(int i = 0; i < n; i++)
            scanf("%d", &t[i]);
        
        for(int i = 0; i < maxn; i++)
            fill(edge[i], edge[i] + maxn, -1);
        
        int tmpx, tmpy, tmpz;
        for(int i = 1; i <= p; i++)
        {
            scanf("%d%d%d", &tmpx, &tmpy, &tmpz);
            edge[tmpx][tmpy] = tmpz;
            edge[tmpy][tmpx] = tmpz;
        }
        
        for(int i = 0; i < (1 << n); i++)
            fill(dp[i] + 1, dp[i] + m + 1, INF);
        
        dp[(1<<n)-1][a] = 0;
        double res = INF;
        for(int s = (1 << n) - 1; s >= 0; s--)
        {
            res = min(res, dp[s][b]);
            for(int i = 0; i < n; i++)
                if((s >> i) & 1)
                    for(int u = 1; u <= m; u++)
                        for(int v = 1; v <= m; v++)
                            if(edge[u][v] >= 0)
                                dp[s&(~(1<<i))][v] = min(dp[s&(~(1<<i))][v], dp[s][u] + (double)edge[u][v] / t[i]);
        }

        if(res == INF) puts("Impossible");
        else printf("%.3lf\n", res);
    }
    return 0;
}

100

101

102

103

104

105

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

filename :c.cpp

author :maksyuki

created time :2017/2/13 8:56:23

last modified :2017/2/13 9:39:35

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 = 30 + 66;

int t[8+66], edge[maxn][maxn];

double dp[1<<9][maxn];

int main()

{

//CFF;

//CPPFF;

int n, m, p, a, b;

while(scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) != EOF)

{

if(!n && !m && !p && !a && !b)

break;

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

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

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

fill(edge[i], edge[i] + maxn, -1);

int tmpx, tmpy, tmpz;

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

{

scanf("%d%d%d", &tmpx, &tmpy, &tmpz);

edge[tmpx][tmpy] = tmpz;

edge[tmpy][tmpx] = tmpz;

}

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

fill(dp[i] + 1, dp[i] + m + 1, INF);

dp[(1<<n)-1][a] = 0;

double res = INF;

for(int s = (1 << n) - 1; s >= 0; s--)

{

res = min(res, dp[s][b]);

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

if((s >> i) & 1)

for(int u = 1; u <= m; u++)

for(int v = 1; v <= m; v++)

if(edge[u][v] >= 0)

dp[s&(~(1<<i))][v] = min(dp[s&(~(1<<i))][v], dp[s][u] + (double)edge[u][v] / t[i]);

}

if(res == INF) puts("Impossible");

else printf("%.3lf\n", res);

}

return 0;

}

poj1745

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

12 2月 2017

Divisibility

Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions: 17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.

You are to write a program that will determine divisibility of sequence of integers.

Input

The first line of the input file contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.

Output

Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.

Sample Input

4 7

17 5 -21 15

Sample Output

Divisible

Source

Northeastern Europe 1999

题目类型：线性DP

算法分析：dp[i][j]表示是否能够使用前i个数字对K取模为j，初始化dp[1][a[1]%K] = true，状态转移方程为if:dp[i-1][j] == true，则dp[i][ (j+a[i])%K] = dp[i][(j-a[i])%K] = true，最后判断dp[N][0]的值即可

/**************************************************
filename       :b.cpp
author         :maksyuki
created time   :2017/2/12 17:58:15
last modified  :2017/2/12 18:54: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 ("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;

bool dp[2][200+66];
int a[10000+66];
int N, K;

int check(int aa, int bb, int flag)
{
    if(flag == 1) aa += bb;
    else aa -= bb;

    aa %= K;
    if(aa < 0) return aa + K;
    else return aa;
}

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

        memset(dp, false, sizeof(dp));
        dp[1&1][check(0,a[1],1)] = true;

        for(int i = 2; i <= N; i++)
        {
            memset(dp[i&1], false, sizeof(dp[i&1]));
            for(int j = 0; j <= K - 1; j++)
                if(dp[(i-1)&1][j])
                {
                    dp[i&1][check(j,a[i],1)] = true;
                    dp[i&1][check(j,a[i],-1)] = true;
                }
        }

        if(dp[N&1][0]) puts("Divisible");
        else puts("Not divisible");
    }
    return 0;
}

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

filename :b.cpp

author :maksyuki

created time :2017/2/12 17:58:15

last modified :2017/2/12 18:54: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 ("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;

bool dp[2][200+66];

int a[10000+66];

int N, K;

int check(int aa, int bb, int flag)

{

if(flag == 1) aa += bb;

else aa -= bb;

aa %= K;

if(aa < 0) return aa + K;

else return aa;

}

int main()

{

//CFF;

//CPPFF;

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

{

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

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

memset(dp, false, sizeof(dp));

dp[1&1][check(0,a[1],1)] = true;

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

{

memset(dp[i&1], false, sizeof(dp[i&1]));

for(int j = 0; j <= K - 1; j++)

if(dp[(i-1)&1][j])

{

dp[i&1][check(j,a[i],1)] = true;

dp[i&1][check(j,a[i],-1)] = true;

}

if(dp[N&1][0]) puts("Divisible");

else puts("Not divisible");

}

return 0;

}

poj1844

maksyuki 发表于 oj 分类，标签: DP-线性DP, 数论-模算术

12 2月 2017

Sum

Consider the natural numbers from 1 to N. By associating to each number a sign (+ or -) and calculating the value of this expression we obtain a sum S. The problem is to determine for a given sum S the minimum number N for which we can obtain S by associating signs for all numbers between 1 to N.

For a given S, find out the minimum value N in order to obtain S according to the conditions of the problem.

Input

The only line contains in the first line a positive integer S (0< S <= 100000) which represents the sum to be obtained.

Output

The output will contain the minimum number N for which the sum S can be obtained.

Sample Input

Sample Output

Hint

The sum 12 can be obtained from at least 7 terms in the following way: 12 = -1+2+3+4+5+6-7.

Source

Romania OI 2002

题目类型：线性DP

算法分析：dp[i][j]表示前1~i的数字通过加减运算是否能够表示成数字j，由于j可能会有负值，所以需要先加上一个偏移量，初始化dp[1][“0”+-1] = true，状态转移方程为dp[i][j] = dp[i-1][j-i] + dp[i-1][j+i]，可以使用奇偶滚动数组来优化空间，写成“我为人人型”会TLE

/**************************************************
filename       :h.cpp
author         :maksyuki
created time   :2017/2/12 12:30:31
last modified  :2017/2/12 13:34:49
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 = 2e5;

bool dp[2][maxn+1];

int main()
{
    //CFF;
    //CPPFF;
    int S;
    while(scanf("%d", &S) != EOF)
    {
        memset(dp[1], false, sizeof(dp[1]));
        dp[1&1][maxn/2+1] = true;
        dp[1&1][maxn/2-1] = true;
        int res = -1;
        for(int i = 2; ; i++)
        {
            memset(dp[i&1], false, sizeof(dp[i&1]));
            for(int j = 0; j <= maxn; j++)
            {
                if(j - i >= 0)
                    dp[i&1][j] |= dp[(i-1)&1][j-i];
                if(j + i <= maxn)
                    dp[i&1][j] |= dp[(i-1)&1][j+i];
            }
            if(dp[i&1][S+maxn/2])     
            {
                res = i;
                break;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

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

filename :h.cpp

author :maksyuki

created time :2017/2/12 12:30:31

last modified :2017/2/12 13:34:49

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 = 2e5;

bool dp[2][maxn+1];

int main()

{

//CFF;

//CPPFF;

int S;

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

{

memset(dp[1], false, sizeof(dp[1]));

dp[1&1][maxn/2+1] = true;

dp[1&1][maxn/2-1] = true;

int res = -1;

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

{

memset(dp[i&1], false, sizeof(dp[i&1]));

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

{

if(j - i >= 0)

dp[i&1][j] |= dp[(i-1)&1][j-i];

if(j + i <= maxn)

dp[i&1][j] |= dp[(i-1)&1][j+i];

}

if(dp[i&1][S+maxn/2])

{

res = i;

break;

}

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

}

return 0;

}

题目类型：同余计算

算法分析：若所有的操作都是累加操作则最后的和是(1 + n) * n / 2，若还存在减法操作则记累减的和为s，则易知有(1 + n) * n / 2 - 2 * s = S，则可推得(1 + n) * n / 2和S关于2同余，则最后枚举n并判断即可

/**************************************************
filename       :i.cpp
author         :maksyuki
created time   :2017/2/12 13:46:56
last modified  :2017/2/12 13:49:02
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 main()
{
    //CFF;
    //CPPFF;
    int n;
    while(scanf("%d", &n) != EOF)
    {
        int res = -1;
        for(int i = (int) sqrt((double)2 * n); ; i++)
            if(i * (i + 1) / 2 >= n && i * (i + 1) / 2 % 2 == n % 2)
            {
                res = i;
                break;
            }
        printf("%d\n", res);
    }
    return 0;
}

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

filename :i.cpp

author :maksyuki

created time :2017/2/12 13:46:56

last modified :2017/2/12 13:49:02

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

{

//CFF;

//CPPFF;

int n;

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

{

int res = -1;

for(int i = (int) sqrt((double)2 * n); ; i++)

if(i * (i + 1) / 2 >= n && i * (i + 1) / 2 % 2 == n % 2)

{

res = i;

break;

}

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

}

return 0;

}

poj2392

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

12 2月 2017

Space Elevator

The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 <= h_i <= 100) and is available in quantity c_i (1 <= c_i <= 10). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i (1 <= a_i <= 40000).

Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.

Input

* Line 1: A single integer, K

* Lines 2..K+1: Each line contains three space-separated integers: h_i, a_i, and c_i. Line i+1 describes block type i.

Output

* Line 1: A single integer H, the maximum height of a tower that can be built

Sample Input

7 40 3

5 23 8

2 52 6

Sample Output

Hint

OUTPUT DETAILS:

From the bottom: 3 blocks of type 2, below 3 of type 1, below 6 of type 3. Stacking 4 blocks of type 2 and 3 of type 1 is not legal, since the top of the last type 1 block would exceed height 40.

Source

USACO 2005 March Gold

题目类型：多重背包

算法分析：这里先使用一个贪心思想是先按照限制高度从小到大排序，然后再直接计算一个多重背包即可

/**************************************************
filename       :g.cpp
author         :maksyuki
created time   :2017/2/12 9:57:26
last modified  :2017/2/12 10:19: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 ("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 = 4e5 + 6666;

struct point
{
    int h, a, c;
    bool operator < (const point &b) const
    {
        return a < b.a;
    }
};

point p[400+66];
int dp[maxn];

int main()
{
    //CFF;
    //CPPFF;
    int K;
    while(scanf("%d", &K) != EOF)
    {
        int W = -INF;
        for(int i = 1; i <= K; i++)
        {
            scanf("%d%d%d", &p[i].h, &p[i].a, &p[i].c);
            W = max(W, p[i].a);
        }

        sort(p + 1, p + 1 + K);
        memset(dp, 0, sizeof(dp));
        
        for(int i = 1; i <= K; i++)
        {
            if(p[i].c * p[i].h >= p[i].a)
            {
                for(int j = p[i].h; j <= p[i].a; j++)
                    dp[j] = max(dp[j], dp[j-p[i].h] + p[i].h);
            }
            else
            {
                int k = 1;
                while(k < p[i].c)
                {
                    for(int j = p[i].a; j >= k * p[i].h; j--)
                        dp[j] = max(dp[j], dp[j-k*p[i].h] + k * p[i].h);
                    p[i].c -= k;
                    k <<= 1;
                }
                for(int j = p[i].a; j >= p[i].c * p[i].h; j--)
                    dp[j] = max(dp[j], dp[j-p[i].c*p[i].h] + p[i].c * p[i].h);
            }
        }
        int res = -INF;
        for(int i = 0; i <= W; i++)
            res = max(res, dp[i]);

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

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

filename :g.cpp

author :maksyuki

created time :2017/2/12 9:57:26

last modified :2017/2/12 10:19: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 ("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 = 4e5 + 6666;

struct point

{

int h, a, c;

bool operator < (const point &b) const

{

return a < b.a;

}

};

point p[400+66];

int dp[maxn];

int main()

{

//CFF;

//CPPFF;

int K;

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

{

int W = -INF;

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

{

scanf("%d%d%d", &p[i].h, &p[i].a, &p[i].c);

W = max(W, p[i].a);

}

sort(p + 1, p + 1 + K);

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

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

{

if(p[i].c * p[i].h >= p[i].a)

{

for(int j = p[i].h; j <= p[i].a; j++)

dp[j] = max(dp[j], dp[j-p[i].h] + p[i].h);

}

else

{

int k = 1;

while(k < p[i].c)

{

for(int j = p[i].a; j >= k * p[i].h; j--)

dp[j] = max(dp[j], dp[j-k*p[i].h] + k * p[i].h);

p[i].c -= k;

k <<= 1;

}

for(int j = p[i].a; j >= p[i].c * p[i].h; j--)

dp[j] = max(dp[j], dp[j-p[i].c*p[i].h] + p[i].c * p[i].h);

}

int res = -INF;

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

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

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

}

return 0;

}

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;

}

poj2184

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

10 2月 2017

Cow Exhibition
"Fat and docile, big and dumb, they look so stupid, they aren't much fun..."
- Cows with Guns by Dana Lyons

The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows. She has given each of the N (1 <= N <= 100) cows a thorough interview and determined two values for each cow: the smartness Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <= 1000) of the cow.

Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si's and, likewise, the total funness TF of the group is the sum of the Fi's. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.

Input

* Line 1: A single integer N, the number of cows

* Lines 2..N+1: Two space-separated integers Si and Fi, respectively the smartness and funness for each cow.

Output

* Line 1: One integer: the optimal sum of TS and TF such that both TS and TF are non-negative. If no subset of the cows has non-negative TS and non- negative TF, print 0.

Sample Input

-5 7

8 -6

6 -3

2 1

-8 -5

Sample Output

Hint

OUTPUT DETAILS:

Bessie chooses cows 1, 3, and 4, giving values of TS = -5+6+2 = 3 and TF
= 7-3+1 = 5, so 3+5 = 8. Note that adding cow 2 would improve the value
of TS+TF to 10, but the new value of TF would be negative, so it is not
allowed.

Source

USACO 2003 Fall

题目类型：01背包

算法分析：详细可以参考http://blog.csdn.net/liuqiyao01/article/details/8753686

/**************************************************
filename       :a.cpp
author         :maksyuki
created time   :2017/2/10 18:38:29
last modified  :2017/2/10 19:02: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 ("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 = 2e5 + 6666;

int v[maxn], w[maxn], dp[maxn];

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

    for(int i = 0; i < maxn; i++)
        dp[i] = -INF;

    int zero = 1e5;
    dp[zero] = 0;
    for(int i = 1; i <= N; i++)
    {
        if(w[i] > 0)
        {
            for(int j = 2e5; j >= w[i]; j--)
                if(dp[j-w[i]] > -INF)
                    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
        else
        {
            for(int j = 0; j <= 2e5 + w[i]; j++)
                if(dp[j-w[i]] > -INF)
                    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }

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

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

filename :a.cpp

author :maksyuki

created time :2017/2/10 18:38:29

last modified :2017/2/10 19:02: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 ("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 = 2e5 + 6666;

int v[maxn], w[maxn], dp[maxn];

int main()

{

//CFF;

//CPPFF;

int N;

scanf("%d", &N);

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

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

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

dp[i] = -INF;

int zero = 1e5;

dp[zero] = 0;

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

{

if(w[i] > 0)

{

for(int j = 2e5; j >= w[i]; j--)

if(dp[j-w[i]] > -INF)

dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

}

else

{

for(int j = 0; j <= 2e5 + w[i]; j++)

if(dp[j-w[i]] > -INF)

dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

}

int res = 0;

for(int i = 1e5; i < 2e5; i++)

if(dp[i] >= 0)

res = max(res, dp[i] + i - 100000);

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

return 0;

}

poj3181

maksyuki 发表于 oj 分类，标签: DP-背包, 组合数学-整数拆分

10 2月 2017

Dollar Dayz
Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are:

1 @ US$3 + 1 @ US$2
1 @ US$3 + 2 @ US$1
1 @ US$2 + 3 @ US$1
2 @ US$2 + 1 @ US$1
5 @ US$1

Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).

Input

A single line with two space-separated integers: N and K.

Output

A single line with a single integer that is the number of unique ways FJ can spend his money.

Sample Input

5 3

Sample Output

Source

USACO 2006 January Silver

题目类型：完全背包

算法分析：dp[i][j]表示使用前i种数字所能够组成的数字j的方案数，初始化dp[0][0] = 1，状态转移方程为dp[i][j] = dp[i-1][j] + dp[i][j-i]，由于最后的结果比较大，所以需要使用高精度计算，这里拼接两个long long长度的变量来存储结果。空间上还可以将第一维优化掉

/**************************************************
filename       :f.cpp
author         :maksyuki
created time   :2017/2/10 10:44:47
last modified  :2017/2/10 16:56:26
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;

LL dpa[1000+66], dpb[1000+66];
LL mod = (LL) 1e18;

int main()
{
    //CFF;
    //CPPFF;
    int N, K;
    scanf("%d%d", &N, &K);
   
    memset(dpa, 0, sizeof(dpa));
    memset(dpb, 0, sizeof(dpb));
    
    dpa[0] = 1;
    for(int i = 1; i <= K; i++)
        for(int j = 0; j <= N; j++)
        {
            if(j - i >= 0)
            {
                dpb[j] = (dpb[j] + dpb[j-i]) + (dpa[j] + dpa[j-i]) / mod;
                dpa[j] = (dpa[j] + dpa[j-i]) % mod;
            }
        }

    if(dpb[N]) printf("%I64d", dpb[N]);
    printf("%I64d\n", dpa[N]);
    return 0;
}

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

filename :f.cpp

author :maksyuki

created time :2017/2/10 10:44:47

last modified :2017/2/10 16:56:26

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;

LL dpa[1000+66], dpb[1000+66];

LL mod = (LL) 1e18;

int main()

{

//CFF;

//CPPFF;

int N, K;

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

memset(dpa, 0, sizeof(dpa));

memset(dpb, 0, sizeof(dpb));

dpa[0] = 1;

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

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

{

if(j - i >= 0)

{

dpb[j] = (dpb[j] + dpb[j-i]) + (dpa[j] + dpa[j-i]) / mod;

dpa[j] = (dpa[j] + dpa[j-i]) % mod;

}

if(dpb[N]) printf("%I64d", dpb[N]);

printf("%I64d\n", dpa[N]);

return 0;

}

hdu1398

maksyuki 发表于 oj 分类，标签: 组合数学-整数拆分

10 2月 2017

Square Coins

People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.
There are four combinations of coins to pay ten credits:

ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.

Your mission is to count the number of ways to pay a given amount using coins of Silverland.

Input

The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.

Output

For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.

Sample Input

Sample Output

Source

Asia 1999, Kyoto (Japan)

题目类型：整数拆分

算法分析：直接使用普通母函数求解即可，注意这里的步长不是每一个递增1

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

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

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 10000 + 7;

const int maxn = 10000 + 66;//注意maxn要大于多项式指数的最高值

int coeff[maxn], temp[maxn];//coeff数组存储多项式各次幂的系数，temp数组存储当前两个多项式相乘的临时结果
const int coin[] = {666, 1 * 1, 2 * 2, 3 * 3, 4 * 4, 5 * 5, 6 * 6, 7 * 7, 8 * 8, 9 * 9, 10 * 10, 11 * 11
, 12 * 12, 13 * 13, 14 * 14, 15 * 15, 16 * 16, 17 * 17};

void Init ()
{
    memset (coeff, 0, sizeof (coeff));
    memset (temp, 0, sizeof (temp));
}

void GenerFunction (long long expnum)//在调用GenerFunction之前一定先调用Init函数
{
    for (long long i = 0; i <= expnum * coin[1]; i += coin[1])
        coeff[i] = 1;

    for (long long i = 2; i <= 17; i++)
    {
        for (long long j = 0; j <= expnum; j++)
        {
            for (long long k = 0; k + j <= expnum; k += coin[i])
                temp[k+j] += coeff[j];
        }

        for (long long j = 0; j <= expnum; j++)
        {
            coeff[j] = temp[j];
            temp[j] = 0;
        }

    }
}

int main()
{
//    ifstream cin ("aaa.txt");

    long long n;

    while (cin >> n)
    {
        if (n == 0)
            break;

        Init ();
        GenerFunction (n);
        cout << coeff[n] << endl;
    }

return 0;
}

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

#define lson rt << 1, l, m

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

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000 + 7;

const int maxn = 10000 + 66;//注意maxn要大于多项式指数的最高值

int coeff[maxn], temp[maxn];//coeff数组存储多项式各次幂的系数，temp数组存储当前两个多项式相乘的临时结果

const int coin[] = {666, 1 * 1, 2 * 2, 3 * 3, 4 * 4, 5 * 5, 6 * 6, 7 * 7, 8 * 8, 9 * 9, 10 * 10, 11 * 11

, 12 * 12, 13 * 13, 14 * 14, 15 * 15, 16 * 16, 17 * 17};

void Init ()

{

memset (coeff, 0, sizeof (coeff));

memset (temp, 0, sizeof (temp));

}

void GenerFunction (long long expnum)//在调用GenerFunction之前一定先调用Init函数

{

for (long long i = 0; i <= expnum * coin[1]; i += coin[1])

coeff[i] = 1;

for (long long i = 2; i <= 17; i++)

{

for (long long j = 0; j <= expnum; j++)

{

for (long long k = 0; k + j <= expnum; k += coin[i])

temp[k+j] += coeff[j];

}

for (long long j = 0; j <= expnum; j++)

{

coeff[j] = temp[j];

temp[j] = 0;

}

int main()

{

// ifstream cin ("aaa.txt");

long long n;

while (cin >> n)

{

if (n == 0)

break;

Init ();

GenerFunction (n);

cout << coeff[n] << endl;

}

return 0;

}

poj3046

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

10 2月 2017

Ant Counting
Bessie was poking around the ant hill one day watching the ants march to and fro while gathering food. She realized that many of the ants were siblings, indistinguishable from one another. She also realized the sometimes only one ant would go for food, sometimes a few, and sometimes all of them. This made for a large number of different sets of ants!

Being a bit mathematical, Bessie started wondering. Bessie noted that the hive has T (1 <= T <= 1,000) families of ants which she labeled 1..T (A ants altogether). Each family had some number Ni (1 <= Ni <= 100) of ants.

How many groups of sizes S, S+1, ..., B (1 <= S <= B <= A) can be formed?

While observing one group, the set of three ant families was seen as {1, 1, 2, 2, 3}, though rarely in that order. The possible sets of marching ants were:

3 sets with 1 ant: {1} {2} {3}
5 sets with 2 ants: {1,1} {1,2} {1,3} {2,2} {2,3}
5 sets with 3 ants: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
3 sets with 4 ants: {1,2,2,3} {1,1,2,2} {1,1,2,3}
1 set with 5 ants: {1,1,2,2,3}

Your job is to count the number of possible sets of ants given the data above.

Input

* Line 1: 4 space-separated integers: T, A, S, and B

* Lines 2..A+1: Each line contains a single integer that is an ant type present in the hive

Output

* Line 1: The number of sets of size S..B (inclusive) that can be created. A set like {1,2} is the same as the set {2,1} and should not be double-counted. Print only the LAST SIX DIGITS of this number, with no leading zeroes or spaces.

Sample Input

3 5 2 3
1
2
2
1
3

Sample Output

Hint

INPUT DETAILS:

Three types of ants (1..3); 5 ants altogether. How many sets of size 2 or size 3 can be made?

OUTPUT DETAILS:

5 sets of ants with two members; 5 more sets of ants with three members

Source

USACO 2005 November Silver

题目类型：线性DP

算法分析：dp[i][j]表示使用前i种蚂蚁构成尺寸为j的集合的个数，初始化dp[0][0] = 1，状态转移方程为dp[i][j] = Simga(dp[i-1][j-k]) k = 0->min(j, a[i]), a[i]为第i种蚂蚁的个数，将求和写成递推形式可得dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1-a[i]]，由于蚂蚁总数比较大，所以需要使用滚动数组来实现，最后累加输出即可。注意相减取模时要先加上模值！！！

/**************************************************
filename       :e.cpp
author         :maksyuki
created time   :2017/2/9 22:50:49
last modified  :2017/2/10 9:44: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 ("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 = 1e6;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

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

int main()
{
    //CFF;
    //CPPFF;
    int T, A, S, B;
    scanf("%d%d%d%d", &T, &A, &S, &B);

    memset(cnt, 0, sizeof(cnt));
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    int tmp;
    for(int i = 1; i <= A; i++)
    {
        scanf("%d", &tmp);
        cnt[tmp]++;
    }
    
    for(int i = 1; i <= T; i++)
    {
        for(int j = 0; j <= B; j++)
        {
            dp[i&1][j] = dp[(i-1)&1][j];
            if(j - 1 >= 0)
                dp[i&1][j] = (dp[i&1][j] + dp[i&1][j-1]) % MOD;
            if(j - 1 - cnt[i] >= 0)
                dp[i&1][j] = (dp[i&1][j] - dp[(i-1)&1][j-1-cnt[i]] + MOD) % MOD;
        }
    }

    int sum = 0;
    for(int i = S; i <= B; i++)
        sum = (sum + dp[T&1][i]) % MOD;
    printf("%d\n", sum);

    return 0;
}

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

filename :e.cpp

author :maksyuki

created time :2017/2/9 22:50:49

last modified :2017/2/10 9:44: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 ("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 = 1e6;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

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

int main()

{

//CFF;

//CPPFF;

int T, A, S, B;

scanf("%d%d%d%d", &T, &A, &S, &B);

memset(cnt, 0, sizeof(cnt));

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

dp[0][0] = 1;

int tmp;

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

{

scanf("%d", &tmp);

cnt[tmp]++;

}

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

{

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

{

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

if(j - 1 >= 0)

dp[i&1][j] = (dp[i&1][j] + dp[i&1][j-1]) % MOD;

if(j - 1 - cnt[i] >= 0)

dp[i&1][j] = (dp[i&1][j] - dp[(i-1)&1][j-1-cnt[i]] + MOD) % MOD;

}

int sum = 0;

for(int i = S; i <= B; i++)

sum = (sum + dp[T&1][i]) % MOD;

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

return 0;

}

超客的水墨烟雨

poj1018

poj2686

poj1745

poj1844

poj2392

poj3666

poj1548

poj1065

poj2184

poj3181

hdu1398

poj3046

分类目录

标签云

书签

近期评论

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