dp 20190618

这个题目是贪心，开始我以为是背包，不过也不太好背包，因为这个L都已经是1e9了。

这个题目怎么贪心呢？它是因为这里有一个二倍的关系，所以说val[i]=val[i-1]*2

所以利用这个关系，我们可以求出每一个体积的最小的花费。

这个处理完之后，我们就可以开始处理题目中的L了。

这个L，从高位开始枚举，先求出L个中最多并且要小于等于这个最大值可以用的这个物品的数量，然后如果是小于，那么再多选一次，这样肯定会超出体积，

不过这样就保证了大于等于L。

对于下面一个L取完膜之后继续这样处理，最后求出最小值。

#include <cstdio>

#include <cstring>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 1e5 + ;

ll val[];

int main()

{

    int n;

    ll L;

    scanf("%d%I64d", &n, &L);

    for (int i = ; i <= n; i++) scanf("%I64d", &val[i]);

    for (int i = ; i <= n; i++) val[i] = min(val[i], val[i - ] * );

    ll ans = inf64, sum = ;

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

    {

        ll len =  << (i - );

        ll num = L / len;

        sum += num * val[i];

        L %= len;

        ans = min(ans, sum + (L > )*val[i]);

    }

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

    return ;

}

B. Dima and a Bad XOR

这个题目其实比较简单，就是找规律，如果找出来了，就很简单了。

首先我发现如果每一行有两个不同的数，那么肯定是可以的，然后lj发现如果最后一行有两个不相同的数，那么肯定也是可以的，最后就可以推出来

如果任意一行有两个数不同，那么肯定也是可以的。

这样子就很简单了。

#include <cstdio>

#include <cstring>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 1e5 + ;

int mp[][];

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    int flag = , mark = ;

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

        for (int j = ; j <= m; j++) {

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

            if (!flag&&j >  && mp[i][j] != mp[i][]) {

                flag = i;

                mark = j;

            }

        }

    }

    if (!flag)

    {

        int ans = ;

        for (int i = ; i <= n; i++) ans ^= mp[i][];

        if (ans == ) printf("NIE\n");

        else

        {

            printf("TAK\n");

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

            printf("1\n");

        }

    }

    else

    {

        printf("TAK\n");

        int ans = ;

        for (int i = ; i <= n; i++) ans ^= mp[i][];

        if(ans)

        {

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

            printf("1\n");

        }

        else

        {

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

            {

                if (i == flag) printf("%d ", mark);

                else printf("1 ");

            }

            printf("\n");

        }

    }

    return ;

}

J 牛客假日团队赛1 分组

这个题目其实很不好想，这个是lj一步步引导我才写出来的，

首先这个题目每一个位置可以往后面推出 1~k 所以算一下复杂度是1e7

dp[i]表示以 i 为最后一个值，从 1~i 的最大的分完组之后的和。

所以这个就有刷表法和填表法，

就是从这个状态往后推和每一个状态从前面推过来，第一个很好写，后面那个比较难。

#include <cstdio>

#include <cstring>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 1e4 + ;

int dp[maxn];

int a[maxn];

int main()

{

    int n, k;

    scanf("%d%d", &n, &k);

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

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

    {

        int mxx = ;

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

        {

            if (i + j > n) break;

            mxx = max(mxx, a[i + j]);

            dp[i + j] = max(dp[i + j], dp[i] + j * mxx);

            //printf("i=%d j=%d dp[%d]=%d\n", i, j, i + j, dp[i + j]);

        }

    }

    printf("%d\n", dp[n]);

    return ;

}

#include <cstdio>

#include <cstring>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 1e4 + ;

int dp[maxn];

int a[maxn];

int main()

{

    int n, k;

    scanf("%d%d", &n, &k);

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

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

    {

        int mxx = ;

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

        {

            if (i < j + ) break;

            mxx = max(mxx, a[i - j]);

            dp[i] = max(dp[i],dp[i - j - ] + mxx * (j + ));

            // printf("i=%d j=%d dp[%d]=%d dp[%d]=%d\n", i, j, i, dp[i],i-j,dp[i-j]);

            // printf("mxx=%d\n", mxx);

        }

    }

    printf("%d\n", dp[n]);

    return ;

}

巴特西

dp 20190618

最新文章

热门文章