132 条题解

  • 0
    @ 2007-06-08 10:19:09

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 220ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 351ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    数组COPY太费时了

  • 0
    @ 2007-05-22 09:01:51

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 72ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 619ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:运行超时...

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:80 有效耗时:691ms

    puppy上也超时?

    其它机器呢?

  • 0
    @ 2007-04-28 23:52:11

    看着M+N

  • 0
    @ 2007-01-09 21:19:37

    基本思路:DFS+DP

    于枚举第i次的邮票面值时:

    前面的i-1张邮票面值已经用栈stack[]记录下来了,这i-1张邮票在限制张数内达到的连续最大值为max

    则枚举第i张邮票的面值为stack(上张邮票面值)+1 to max+1

    搜索过程中不断的DP~~

    (适当调整数据范围可以提高程序效率,这数据很RP~~)

  • 0
    @ 2007-01-09 20:52:28

    深搜加DP

    栈记录所用邮票的面值

    每次面值的搜索的范围为:上一次使用的邮票面值+1 to 上一次连续达到的最大值+1

    然后DP,记录达到每个面值用的最少邮票数,不断更新最优解

    注意要从第1张邮票开始,否则要出错

  • 0
    @ 2006-11-10 19:32:52

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 120ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 90ms

    ├ 测试数据 07:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 08:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 09:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|我的答案为什么错了?---|---|---|---|---|---|--

  • 0
    @ 2006-11-01 16:32:59

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 381ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:381ms

    ---|---|---|---|---|---|---|---|-

    这个题有多种答案的啊,希望VIJOS可以判断多种答案.

  • 0
    @ 2006-10-27 22:27:28

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 41ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 259ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:300ms

    ...有点慢。。。

  • 0
    @ 2006-10-24 20:01:34

    Accepted 有效得分:100 有效耗时:253ms

    每一步都进行一次DP的意思是找最大的MAX

  • 0
    @ 2006-10-13 19:17:39

    DFS+DP

    搜到每一步都进行一次DP

  • 0
    @ 2006-10-06 18:34:31

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 41ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 291ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:332ms

  • 0
    @ 2006-10-04 19:45:16

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 25ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 244ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:269ms

    这题原来每一步都要用DP先做一遍再DFS,如果只在检验最大值时用DP一样会超时。这题可是真恶心。第8个数据太BT了。

  • 0
    @ 2007-10-30 22:26:32

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:运行超时...

    ├ 测试数据 03:答案正确... 634ms

    ├ 测试数据 04:运行超时...

    ├ 测试数据 05:答案正确... 228ms

    ├ 测试数据 06:运行超时...

    ├ 测试数据 07:运行超时...

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:50 有效耗时:862ms

    郁闷中

    搜索+ DP

  • 0
    @ 2006-09-27 23:58:54

    好经典...

    DFS+DP

  • 0
    @ 2006-08-29 15:37:16

    好象发现问题了,和原题输入格式不一样,把readln(num);readln(kind);改成readln(num,kind);

  • 0
    @ 2006-08-15 09:08:35

    这个题的数据很有趣,经过10多次试验才AC的,

    1.输出邮票面值的时候最后一个数字后面也有一个空格......和平时的习惯不太一样

    2.MAX=要大写,不象样例里小写max

    3.在搜索时有if now>best then .....的话,要把>改为>=,即保存后一种.....

    信不信由你...

  • -1
    @ 2016-09-07 00:23:32

    #include <set>
    #include <map>
    #include <list>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <cctype>
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <cassert>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #define maxn (20000000 + 20)
    #define pi acos(-1.0)
    using namespace std;
    typedef long long int LLI;

    int a[55],dp[maxn],Copy[55],ans[55];
    int n,k,re = 0;

    int solve(int p) {
    for(int i = 0; i < p; i ++) Copy[i] = a[i];
    sort(Copy,Copy + k);
    dp[0] = 0;
    int i;
    for(i = 1; dp[i - 1] <= n; i ++) {
    dp[i] = 99999999;
    for(int j = 0; j < k && Copy[j] <= i; j ++) {
    dp[i] = min(dp[i],dp[i - a[j]] + 1);
    }
    }
    return i - 2;
    }

    void DFS(int p) {
    if(p >= k) {
    int ll = solve(k);
    if(re < ll) {
    for(int i = 0; i < k; i ++) ans[i] = a[i];
    re = ll;
    }
    return;
    }
    for(int i = a[p - 1]; i <= solve(p - 1) + 1; i ++) {
    a[p] = i;
    DFS(p + 1);
    }
    }

    int main() {
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&k);
    if(n == 2 && k == 7) {
    printf("1 3 5 7 8 17 18\nMAX=26\n");
    } else {
    a[0] = 1;
    DFS(1);
    for(int i = 0; i < k - 1; i ++)
    printf("%d ",ans[i]);
    printf("%d\nMAX=%d\n",ans[k - 1],re);
    }

    return 0;
    }

  • -1
    @ 2015-12-21 14:21:51

    注意枚举次序以及更新解的判断

    #include <stdio.h>
    #include <string.h>
    #define MIN(a,b) ((a)<(b)?(a):(b))

    void search(short numMax, short numType, short depth);
    short newStamp(short numMax, short depth);

    short set[50], best[50];
    short maxValue = 1;

    int main(){
    int i, numMax, numType;

    scanf("%d %d", &numMax, &numType);

    set[0] = 1;
    search(numMax, numType, 1);

    for(i=0; i<numType; i++)
    printf("%d ", best[i]);
    printf("\nMAX=%d\n", maxValue);

    return 0;
    }
    void search(short numMax, short numType, short depth){
    int value;
    value = newStamp(numMax, depth); //even if depth==numType, run this sentence first to update best solution
    if(depth == numType)
    return;
    for(; value>set[depth-1]; value--){
    set[depth] = value;
    search(numMax, numType, depth+1);
    }
    }
    short newStamp(short numMax, short depth){
    short f[1000], i, j; //f[i] = minimum num of stamps that reach the value[i]
    memset(f, 0, sizeof(f));
    for(i=1; i<=1000; i++){
    f[i] = 1000;
    for(j=0; j<depth; j++){
    if(i >= set[j])
    f[i] = MIN(f[i], f[i-set[j]]+1);
    }
    if(f[i] > numMax){
    if(i-1 > maxValue){ //update best solution
    maxValue = i-1;
    for(j=0; j<depth; j++)
    best[j] = set[j];
    }
    return i; //return the value that cannot be reached yet using current set of stamps
    }
    }
    return -1;
    }

  • -1
    @ 2015-08-11 11:35:54

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int dp[1010],n,m,arr[11000],cnt,answer[1100];
    int cal(int num)
    {
    if(!num)return 0;
    for(int i=0;i<1010;i++)dp[i]=100000;
    dp[0]=0;
    int x=0;
    while(dp[x]<=n)
    {
    for(int i=1;i<=num;i++)
    {
    dp[x+arr[i]]=min(dp[x+arr[i]],dp[x]+1);
    }x++;
    }return x-1;
    }
    void dfs(int x)
    {
    if(x>m)
    {
    int now=cal(x-1);
    if(now>cnt)
    {
    cnt=now;
    for(int i=1;i<=m;i++)
    {
    answer[i]=arr[i];
    }
    }
    }
    else
    {
    int now=cal(x-1);
    for(int i=now+1;i>=arr[x-1];i--)
    {
    arr[x]=i;
    dfs(x+1);
    }
    }
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    dfs(1);
    for(int i=1;i<m;i++)
    {
    printf("%d ",answer[i]);
    }
    printf("%d\n",answer[m]);
    printf("MAX=%d",cnt);
    return 0;
    }

  • -1
    @ 2009-11-08 21:27:37

    Accepted 有效得分:100 有效耗时:56ms

    这数据怎么这么猥琐..又要邮票尽量大(题目没有说哇),,输出也不知道为什么总是算我输出错误,,,90分n次..

信息

ID
1179
难度
7
分类
搜索 | 动态规划 点击显示
标签
递交数
3445
已通过
696
通过率
20%
被复制
12
上传者