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

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;

}

超客的水墨烟雨

poj1745

poj1844

poj2392

分类目录

标签云

书签

近期评论

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