hdu2188

maksyuki 发表于 oj 分类，标签: 博弈-Bash

15 9月 2015

悼念512汶川大地震遇难同胞——选拔志愿者

Problem Description

对于四川同胞遭受的灾难，全国人民纷纷伸出援助之手，几乎每个省市都派出了大量的救援人员，这其中包括抢险救灾的武警部队，治疗和防疫的医护人员，以及进行心理疏导的心理学专家。根据要求，我校也有一个奔赴灾区救灾阅读全文 »

hdu2152

maksyuki 发表于 oj 分类，标签: 组合数学-普通母函数

15 9月 2015

Fruit

Problem Description

转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。

于是，很多人们慕名而来，找Lele买水果。阅读全文 »

hdu2149

maksyuki 发表于 oj 分类，标签: 博弈-Bash

15 9月 2015

Public Sale

Problem Description

虽然不想，但是现实总归是现实，Lele始终没有逃过退学的命运，阅读全文 »

hdu2141

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

15 9月 2015

Can you find it?

Problem Description

Give you three sequences of numbers A, B, C, then we 阅读全文 »

hdu2138

maksyuki 发表于 oj 分类，标签: 数论-大素数测试

15 9月 2015

How many prime numbers

Problem Description

Give you a lot of positive integers, just to find out how many prime numbers there are. 阅读全文 »

分拆素数和

Problem Description

把一个偶数拆成两个不同素数的和，有几种拆法呢？

Input

输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。阅读全文 »

hdu2067

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

15 9月 2015

小兔的棋盘

Problem Description

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧! 阅读全文 »

hdu2051

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

15 9月 2015

Bitset

Problem Description

Give you a number on base ten,you should output it on base two.(0 < n < 1000)

Input

For each case there is a postive number n on base ten, end 阅读全文 »

hdu2044

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

15 9月 2015

一只小蜜蜂...

Problem Description

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。阅读全文 »

hdu1950

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

15 9月 2015

Bridging signals

Problem Description

'Oh no, they've done it again', cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too
expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without rossing each other, is imminent. Bearing in mind that there may be housands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?

Figure 1. To the left: The two blocks' ports and their signal mapping (4,2,6,3,1,5). To the right: At most three signals may be routed on the silicon surface without crossing each other. The dashed signals must be bridged.

A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number pecifies which port on the right side should be connected to the i:th port on the left side.
Two signals cross if and only if the straight lines connecting the two ports of each pair do.

Input

On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer p<40000, the number of ports on the two functional blocks. Then follow p lines, describing the signal mapping: On the i:th line is the port number of the block on the right side which should be connected to the i:th port of the block on the left side.

Output

For each test scenario, output one line containing the maximum number of signals which may be routed on the silicon surface without crossing each other.

Sample Input

Sample Output

Source

NWERC2003

题目类型：LIS

算法分析：直接使用LIS求解即可

#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 int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 500000 + 666;

int ans[maxn], b[maxn], LEN;

//用二分查找的方法找到一个位置，使得num>b[i-1] 并且num<b[i],并用num代替b[i]
int Search (int num,int low,int high)
{
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(num>=b[mid])  low=mid+1;
        else   high=mid-1;
    }
    return low;
}


int LIS (int n)
{
    int i, len, pos;
    b[1] = ans[1];
    len = 1;
    for (i = 2;i <= n; i++)
    {
        if(ans[i] >= b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可
        {
            len++;
            b[len] = ans[i];
        }

        else//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置
        {
            pos = Search (ans[i], 1, len);
            b[pos] = ans[i];
        }
    }

return len;
}



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

    int t;
    scanf ("%d", &t);

    while (t--)
    {
        int  n;
        scanf ("%d", &n);

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

        printf ("%d\n", LIS (n));
    }

return 0;
}

100

101

102

#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 int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 500000 + 666;

int ans[maxn], b[maxn], LEN;

//用二分查找的方法找到一个位置，使得num>b[i-1] 并且num<b[i],并用num代替b[i]

int Search (int num,int low,int high)

{

int mid;

while(low<=high)

{

mid=(low+high)/2;

if(num>=b[mid]) low=mid+1;

else high=mid-1;

}

return low;

}

int LIS (int n)

{

int i, len, pos;

b[1] = ans[1];

len = 1;

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

{

if(ans[i] >= b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可

{

len++;

b[len] = ans[i];

}

else//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置

{

pos = Search (ans[i], 1, len);

b[pos] = ans[i];

}

return len;

}

int main()

{

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

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

int t;

scanf ("%d", &t);

while (t--)

{

int n;

scanf ("%d", &n);

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

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

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

}

return 0;

}

hdu1863

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

15 9月 2015

畅通工程

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查阅读全文 »

hdu1846

maksyuki 发表于 oj 分类，标签: 博弈-Bash

15 9月 2015

Brave Game

Problem Description

十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。阅读全文 »

hdu1792

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

15 9月 2015

A New Change Problem

Problem Description

Now given two kinds of coins A and B,which satisfy that GCD(A,B)=1. 阅读全文 »

hdu1788

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

15 9月 2015

Chinese remainder theorem again

Problem Description

我知道部分同学最近在看中国剩余定理，就这个定理本身，还是比较简单的：
假设m1,m2,…,mk两两互素，则下面同余方程组：阅读全文 »

hdu1754

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

15 9月 2015

I Hate It

Problem Description

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

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

hdu1712

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

15 9月 2015

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;

}

返回首页上一页 8 9 10 11 12 下一页最后一页

超客的水墨烟雨

hdu2188

悼念512汶川大地震遇难同胞——选拔志愿者

hdu2152

Fruit

hdu2149

Public Sale

hdu2141

Can you find it?

hdu2138

How many prime numbers

hdu2098

分拆素数和

hdu2067

小兔的棋盘

hdu2051

Bitset

hdu2044

一只小蜜蜂...

hdu1950

Bridging signals

hdu1863

畅通工程

hdu1846

Brave Game

hdu1792

A New Change Problem

hdu1788

Chinese remainder theorem again

hdu1754

I Hate It

hdu1712

ACboy needs your help

分类目录

标签云

书签

近期评论

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