noip模拟赛遭遇

分析：暴力挺好打的，对于前30%的数据神搜，hi相同的数据将所有的建筑按照c从小到大排序，看最多能跳多少,ci=0的数据将所有的建筑按照h从小到大排序，枚举起点和终点，看能否跳这么多,取个max就可以了.这样70分就到手了.

部分分的提示还是比较明显的，要消除一个参数的影响，那么就按照h从小到大排序，显然只有可能顺着跳过城市，不能跳过去又跳回来.那么就是一个比较简单的dp了：f[i][j]表示跳了i次，最后一次跳到j的最小花费，转移的话枚举j之前的k就能转移了，最后倒叙枚举i看哪一个f[i][j]<=T就可以了.

多个参数有影响的常见策略是消除一个参数的影响，常见的办法就是排序,如果一个点不能经过多次，那么就想一个办法让它强行不经过这个点.

暴力：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, T, ans, vis[];

bool flag1 = true, flag2 = true;

struct node

{

    int c, h;

}e[];

bool cmp1(node a, node b)

{

    return a.c < b.c;

}

bool cmp2(node a, node b)

{

    return a.h < b.h;

}

void dfs(int u, int sum,int tot)

{

    ans = max(ans, tot + );

    vis[u] = ;

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

    {

        if (!vis[i])

        {

            int huafei = abs(e[i].h - e[u].h) + e[u].c;

            if (sum + huafei <= T)

            dfs(i, sum + huafei, tot + );

        }

    }

}

int main()

{

    scanf("%d", &n);

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

    {

        scanf("%d", &e[i].c);

        if (e[i].c != )

            flag2 = false;

    }

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

    {

        scanf("%d", &e[i].h);

        if (i !=  && e[i].h != e[i - ].h)

            flag1 = false;

    }

    scanf("%d", &T);

    if (n <=  || (!flag1 && !flag2))

    {

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

        {

            memset(vis, , sizeof(vis));

            dfs(i,,);

        }

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

    }

    else

        if (flag1)

        {

            sort(e + , e +  + n, cmp1);

            int res = , cur = ;

            while (cur <= n && res <= T)

            {

                ans++;

                res += e[cur].c;

                cur++;

            }

            printf("%d\n", ans - );

        }

        else

        {

            sort(e + , e +  + n, cmp2);

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

            {

                int j = i + , res = ;

                while (j <= n && res <= T)

                {

                    res += abs(e[j].h - e[j-].h);

                    j++;

                }

                ans = max(ans, j - i + );

            }

            printf("%d\n", ans - );

        }

    return ;

}

正解：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n,T;

int f[][];

struct node

{

    int c, h;

}e[];

bool cmp(node a, node b)

{

    return a.h < b.h;

}

int main()

{

    memset(f,  / , sizeof(f));

    scanf("%d", &n);

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

        scanf("%d", &e[i].c);

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

        scanf("%d", &e[i].h);

    scanf("%d", &T);

    sort(e + , e +  + n, cmp);

    f[][] = e[].c;

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

        for (int j = ; j <= n; j++)

            for (int k = j + ; k <= n; k++)

                f[i + ][k] = min(f[i + ][k], f[i][j] + e[k].h - e[j].h + e[k].c);

    for (int i = n; i >= ; i--)

        for (int j = ; j <= n; j++)

            if (f[i][j] <= T)

            {

                printf("%d\n", i + );

                return ;

            }

    printf("0\n");

    return ;

}

巴特西

noip模拟赛遭遇

最新文章

热门文章

巴特西

noip模拟赛 遭遇

最新文章

热门文章

noip模拟赛遭遇