hdu1754

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

15 9月 2015

I Hate It

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序阅读全文 »

ACboy needs your help

Problem Description

ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.

Output

For each data set, your program should output a line which contains the number of the max profit ACboy will gain.

Sample Input

2 2

1 2

1 3

2 2

2 1

2 3

3 2 1

0 0

Sample Output

Source

HDU 2007-Spring Programming Contest

题目类型：分组背包

算法分析： 每一个人分为一组，每组中的物品由不同时间(花费)来区分，然后直接使用分组背包求解即可，注意一定要先判断j >= k !!!!!!

#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 = 7;
const int maxn = 500 + 66;

int ans[maxn][maxn], dp[maxn];

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

    int n, m;
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0)
            break;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> ans[i][j];


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

        for (int i = 1; i <= n; i++)
        {
            for (int j = m; j >= 0; j--)
            {
                for (int k = 1; k <= m; k++)
                {
                    if (j >= k)
                        dp[j] = max (dp[j], dp[j-k] + ans[i][k]);
                }
            }
        }

        int maxval = -INF;
        for (int i = 0; i <= m; i++)
            maxval = max (maxval, dp[i]);

        cout << maxval << 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 = 7;

const int maxn = 500 + 66;

int ans[maxn][maxn], dp[maxn];

int main()

{

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

int n, m;

while (cin >> n >> m)

{

if (n == 0 && m == 0)

break;

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

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

cin >> ans[i][j];

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

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

{

for (int j = m; j >= 0; j--)

{

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

{

if (j >= k)

dp[j] = max (dp[j], dp[j-k] + ans[i][k]);

}

int maxval = -INF;

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

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

cout << maxval << endl;

}

return 0;

}

hdu1698

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

15 9月 2015

Just a Hook

Problem Description

In the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length. 阅读全文 »

hdu1671

maksyuki 发表于 oj 分类，标签: 字符串-Trie树

15 9月 2015

Phone List

Problem Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone 阅读全文 »

hdu1576

maksyuki 发表于 oj 分类，标签: 数论-乘法逆元

15 9月 2015

A/B

Problem Description

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给阅读全文 »

hdu1573

maksyuki 发表于 oj 分类，标签: 数论-线性同余方程(组)

15 9月 2015

X问题

Problem Description

求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。

Input

输入数据的第一行为一个正整数T，表示有T组测试数据。每组测试阅读全文 »

hdu1421

maksyuki 发表于 oj 分类，标签: DP-线性DP, 基础算法-贪心

15 9月 2015

搬寝室

Problem Description

搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比阅读全文 »

hdu1395

maksyuki 发表于 oj 分类，标签: 基础算法-枚举, 数论-欧拉定理

15 9月 2015

2^x mod n = 1

Problem Description

Give a number n, find the minimum x(x>0) that satisfies 2^x mod n = 1. 阅读全文 »

hdu1251

maksyuki 发表于 oj 分类，标签: 字符串-Trie树

15 9月 2015

统计难题

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量阅读全文 »

hdu1240

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

15 9月 2015

Asteroids!

Problem Description

You're in space. 阅读全文 »

hdu1238

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

15 9月 2015

Substrings

Problem Description

You are given a number of case-sensitive strings of alphabetic characters, 阅读全文 »

hdu1232

maksyuki 发表于 oj 分类，标签: 数据结构-并查集

15 9月 2015

畅通工程

Problem Description

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通阅读全文 »

hdu1166

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

15 9月 2015

敌兵布阵

Problem Description

C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务阅读全文 »

hdu1164

maksyuki 发表于 oj 分类，标签: 数论-素因子分解

15 9月 2015

Eddy's research I

Problem Description

Eddy's interest is very extensive, recently he is interested in prime number. Eddy discover the all number owned can be divided into the multiply of prime number, but he can't write program, so Eddy has to ask intelligent you to help him, he asks you to write a program which can do the number to divided into the multiply of prime number factor .

Input

The input will contain a number 1 < x<= 65535 per line representing the number of elements of the set.

Output

You have to print a line in the output for each entry with the answer to the previous question.

Sample Input

9412

Sample Output

112*2*13*181

Author

eddy

题目类型：整数素因子分解

算法分析：由于被分解的整数比较小，所以可以使用试除法进行整数分解

#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 = 7;
const int maxn = 10000 + 66;

bool is_first;

void GetFactor (long long val)
{
    for (int i = 2; i * i <= val; i++)
    {
        while (val % i == 0)
        {
            if (is_first)
            {
                is_first = false;
                cout << i;
            }

            else
                cout << "*" << i;

            val /= i;
        }
    }

    if (val != 1)
    {
        if (is_first)
        {
            is_first = false;
            cout << val;
        }

        else
            cout << "*" << val;
    }
    cout << endl;
}


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

    long long n;
    while (cin >> n)
    {
        is_first = true;
        GetFactor (n);
    }

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

const int maxn = 10000 + 66;

bool is_first;

void GetFactor (long long val)

{

for (int i = 2; i * i <= val; i++)

{

while (val % i == 0)

{

if (is_first)

{

is_first = false;

cout << i;

}

else

cout << "*" << i;

val /= i;

}

if (val != 1)

{

if (is_first)

{

is_first = false;

cout << val;

}

else

cout << "*" << val;

}

cout << endl;

}

int main()

{

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

long long n;

while (cin >> n)

{

is_first = true;

GetFactor (n);

}

return 0;

}

hdu1160

maksyuki 发表于 oj 分类，标签: DP-线性DP, 基础算法-贪心

15 9月 2015

FatMouse's Speed

Problem Description

FatMouse believes that the fatter a mouse is, the faster it runs. To disprove 阅读全文 »

hdu1159

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

15 9月 2015

Common Subsequence

Problem Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc abfcab

programming contest

abcd mnp

Sample Output

Source

Southeastern Europe 2003

Recommend

Ignatius

题目类型：线性DP

算法分析：最长公共子序列的模板题，直接求解即可

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

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

int dp[maxn][maxn];
char sa[maxn], sb[maxn];

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    while (cin>> (sa + 1) >> (sb + 1))
	{
        int lena = strlen (sa + 1), lenb = strlen(sb + 1);
        for (int i = 0; i <= lena; i++)
            dp[i][0] = 0;

		for (int i = 0; i <= lenb; i++)
			dp[0][i] = 0;

		for (int i = 1; i <= lena; i++)
		{
			for(int j = 1; j <= lenb; j++)
			{
                if (sa[i] == sb[j])
					dp[i][j] = dp[i-1][j-1] + 1;

				else
					dp[i][j] = max (dp[i-1][j], dp[i][j-1]);
			}
		}

		cout << dp[lena][lenb] << 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>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2000 + 66;

int dp[maxn][maxn];

char sa[maxn], sb[maxn];

int main()

{

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

// freopen ("aaa.txt", "r", stdin);

while (cin>> (sa + 1) >> (sb + 1))

{

int lena = strlen (sa + 1), lenb = strlen(sb + 1);

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

dp[i][0] = 0;

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

dp[0][i] = 0;

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

{

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

{

if (sa[i] == sb[j])

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

else

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

}

cout << dp[lena][lenb] << endl;

}

return 0;

}

返回首页上一页 10 11 12 13 14 下一页最后一页

超客的水墨烟雨

hdu1754

I Hate It

hdu1712

ACboy needs your help

hdu1698

Just a Hook

hdu1671

Phone List

hdu1576

A/B

hdu1573

X问题

hdu1421

搬寝室

hdu1395

2^x mod n = 1

hdu1251

统计难题

hdu1240

Asteroids!

hdu1238

Substrings

hdu1232

畅通工程

hdu1166

敌兵布阵

hdu1164

Eddy's research I

hdu1160

FatMouse's Speed

hdu1159

Common Subsequence

分类目录

标签云

书签

近期评论

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