题解

191 条题解

  • 0
    @ 2006-10-26 09:22:46

    编译通过...

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

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

     ├ 错误行输出

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

     ├ 错误行输出

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

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

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

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

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

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

     ├ 错误行输出

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

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

    Unaccepted 有效得分:70 有效耗时:0ms

  • 0
    @ 2006-10-25 21:02:57

    纯rp算法AC!

    把数据分别放入两个数组

    随机枚举两个数(每个数组一个),交换,算差值,记录,…………

    重复1000000次………………

  • 0
    @ 2006-10-24 16:52:53

    开始把题目想简单了...用最简单的装箱DP做的...只对了4个点...

    懒的重写,只能用指针配合DP,无奈算法太虚,第8点超时(第6个点也800MS+)...

    最终必杀--CHEAT!汗...表BS我...

  • 0
    @ 2006-10-22 10:23:29

    贪心就可以了!!!!!

  • 0
    @ 2006-09-28 20:19:55

    奇迹,我的O(N*N*TOTAL)居然也能过!可能是剪枝太强了吧,呵呵。

  • 0
    @ 2006-09-21 21:17:10

    谁有 O(n*tot) 的程序啊?

  • 0
    @ 2006-09-04 18:05:01

    怎么用Hash优化?

  • 0
    @ 2006-07-09 09:15:37

    我的DP本应该超时的(一个 FOR 200 套一个 FOR 8000)。可居然没超时,而且只有最后一个数据用了9MS,其他都是0MS。

    只是第二个数据WA了。有哪位仁兄能把第二个数据发一下的???

  • 0
    @ 2006-06-12 10:25:05

    直接dp果然超时

    要用hash表优化一下

  • -1
    @ 2016-09-18 20:32:40

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n;
    int a[207];
    bool dp[207][8005];
    int sum;
    int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>a[i];
    sum+=a[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
    for(int j=n/2;j>=0;j--){
    for(int k=sum/2;k>=0;k--){
    if(dp[j][k]==1)dp[j+1][k+a[i]]=1;
    }
    }
    }
    for(int i=sum/2;i>=0;i--){
    if(dp[n/2][i]==1){
    cout<<i<<" "<<sum-i;
    break;
    }
    }
    return 0;
    }

    • @ 2016-12-23 21:04:54

      询问一下,此题DP定义的是什么意思?

  • -1
    @ 2016-08-25 17:58:09

    bitset+滚动

    编译成功

    • 测试数据 #0: Accepted, time = 0 ms, mem = 772 KiB, score = 10
    • 测试数据 #1: Accepted, time = 0 ms, mem = 768 KiB, score = 10
    • 测试数据 #2: Accepted, time = 0 ms, mem = 768 KiB, score = 10
    • 测试数据 #3: Accepted, time = 0 ms, mem = 768 KiB, score = 10
    • 测试数据 #4: Accepted, time = 15 ms, mem = 772 KiB, score = 10
    • 测试数据 #5: Accepted, time = 15 ms, mem = 768 KiB, score = 10
    • 测试数据 #6: Accepted, time = 0 ms, mem = 768 KiB, score = 10
    • 测试数据 #7: Accepted, time = 15 ms, mem = 772 KiB, score = 10
    • 测试数据 #8: Accepted, time = 15 ms, mem = 768 KiB, score = 10
    • 测试数据 #9: Accepted, time = 15 ms, mem = 768 KiB, score = 10

    Accepted, time = 75 ms, mem = 772 KiB, score = 100

    #include <bits/stdc++.h>
    using namespace std;
    
    bitset<8000> dp[2][105];
    int a[205];
    int main()
    {
            int n, s = 0;
            scanf("%d", &n);
            for (int i = 1; i <= n; i++) {
                    scanf("%d", &a[i]);
                    s += a[i];
            }
            memset(dp, 0, sizeof dp);
            int now = 1, pre = 0;
            dp[pre][0][0] = 1;
            for (int i = 1; i <= n; i++) {
                    for (int j = 0; j < 105 && j <= i; j++) {
                            dp[now][j] = dp[pre][j] | (dp[pre][j-1] << a[i]);
                            //cout << i << " " << j << " " << dp[now][j] << endl;
                    }
                    swap(now, pre);
            }
            int ans = 0;
            for (int i = 0; i <= n; i++)
                    for (int k = 0; k < s; k++)
                            if (dp[pre][i][k] && abs(n-i-i) <= 1 && abs(s-k-k) < abs(s-ans-ans))
                                    ans = k;
            int ans2 = s-ans;
            if (ans > ans2) swap(ans, ans2);
            cout << ans << " " << ans2 << endl;
            return 0;
    }
    
    

信息

ID
1153
难度
7
分类
动态规划 | 背包 点击显示
标签
递交数
4720
已通过
1026
通过率
22%
被复制
6
上传者