UOJ Logo z2512690268的博客

博客

小A的题解(高一考试T4题解)

2018-08-28 12:00:01 By z2512690268

小A是很守信用滴!为了感谢你的帮助,他决定将“secret”的题解通过z2512690268的账号发到博客里。

算法一

最简单的搜索与回溯,看一眼就应该有的想法,良心出题人实力送分。预期得分:50~70分(不像T5的某人,出的题用暴力只给40。。。至于正解,我坚决怀疑你们没学!!!)

dfs_without_optimize.cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1100;
int n, money, val[maxn], cost[maxn], ans;
void dfs(int x, int pay, int gain){
    if(pay > money)    return ;
    if(x == n + 1){
        ans = max(ans, gain);
        return ;
    }
    dfs(x + 1, pay + cost[x], gain + val[x]);
    dfs(x + 1, pay, gain);
}
int main(void){
//    freopen("secret.in", "r", stdin);
//    freopen("secret.out", "w", stdout);
    scanf("%d%d", &n, &money);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", val + i, cost + i);
    dfs(1, 0, 0);
    printf("%d\n", ans);
}

算法二

不加优化的dfs不是好暴力!可以观察算法一中的剪枝条件(pay>money),可以发现,只要让pay超过money更早,就可以裁剪大量分支,起到更好的剪枝效果。而pay是已选择的文件的总花费时间,要令它尽量变大,就要让程序先选择耗时较多的文件,改变搜索顺序,效率可以得到很大提高,可以A过这道题。预期得分:100分

dfs_with_optimize.cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1100;
int n, money, ans;
struct sec{
    int val;
    int cost;
}secs[maxn];
bool cmp(const sec& A, const sec& B){
    return A.cost > B.cost;
}
void dfs(int x, int pay, int gain){
    if(pay > money)    return ;
    if(x == n + 1){
        ans = max(ans, gain);
        return ;
    }
    dfs(x + 1, pay + secs[x].cost, gain + secs[x].val);
    dfs(x + 1, pay, gain);
}
int main(void){
//    freopen("secret.in", "r", stdin);
//    freopen("secret.out", "w", stdout);
    scanf("%d%d", &n, &money);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &secs[i].val, &secs[i].cost);
    sort(secs + 1, secs + n + 1, cmp);
    dfs(1, 0, 0);
    printf("%d\n", ans);
}

算法三

超前学习的同学们有福了,赤果果的背包dp有木有!如果你会背包,这道题送分没毛病。预期得分100分

dp.cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1100;
const int maxm = 500010;
int n, money, val[maxn], cost[maxn], dp[maxm];
void DP(){
    for(int i = 1; i <= n; ++i)
        for(int j = money; j >= cost[i]; --j)
            dp[j] = max(dp[j], dp[j - cost[i]] + val[i]);
}
int main(void){
//    freopen("secret.in", "r", stdin);
//    freopen("secret.out", "w", stdout);
    scanf("%d%d", &n, &money);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", val + i, cost + i);
    DP();    
    printf("%d\n", dp[money]);
}

算法四

虽说算法二成功AC了,但我们发现它的耗时是算法3的70倍!这在数据较大时是简直无法忍受的。因此,我们要考虑考虑更多的剪枝条件。我们考虑搜索到第x个的情况,如果我们已经预处理出了从第x个到最后一个文件中价值最大的一个的价值,那么如果我们将后面的所有文件都用最大价值取得还没有超过当前已经搜索到的最大值,再搜索下去就没有任何意义了,也就是说,一旦出现这种情况立刻返回上一层,就能够节省大量的无用功,加快速度。这样优化后,用时就只有dp的三到四倍了。

dfs_with_more_optimize.cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 35;
int n, money, ans, maxx[maxn], minn[maxn];
struct sec{
    int val;
    int cost;
}secs[maxn];
bool cmp(const sec& A, const sec& B){
    return A.cost > B.cost;
}
void dfs(int x, int pay, int gain){
    if(pay > money)    return ;
    if(gain + maxx[x] * (n - x + 1) <= ans)            return ;
    if(x == n + 1){
        ans = max(ans, gain);
        return ;
    }
    dfs(x + 1, pay + secs[x].cost, gain + secs[x].val);
    dfs(x + 1, pay, gain);
}
int main(void){
//    freopen("secret.in", "r", stdin);
//    freopen("secret.out", "w", stdout);
    scanf("%d%d", &n, &money);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &secs[i].val, &secs[i].cost);
    sort(secs + 1, secs + n + 1, cmp);
    for(int i = n; i >= 1; --i)
        maxx[i] = max(secs[i].val, maxx[i + 1]);
    dfs(1, 0, 0);
    printf("%d\n", ans);
}

算法5~正无穷

其实深搜还有几种优化的方法在这篇题解里就不再赘述了。要知道,dfs优化的方法是十分灵活而种类繁多的,通过大量做题与学习还有更多的剪枝技巧可以用在这道题上。所以说,不会算法并不一定解决不了问题,只要善于剪枝,暴力也能轻松AC。

最后附上数据生成器,大家自己探索更优的dfs优化或其他算法吧。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
int main(void){
    freopen("secret.in", "w", stdout);
    long long n = 30;
    cout << n << " ";
    srand(time(NULL));
    cout << rand() * (n >> 1) << endl;
    for(int i = 1; i <= n; ++i)
        cout << rand() << " " << rand() << endl;
}

评论

insilent
前排兹瓷

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。