小编Shu*_*rma的帖子

所以,这个问题我没有任何线索如何解决它的问题陈述是:

给定N个整数的集合S,任务决定是否可以将它们划分为K个非空子集,使得每个K个子集中的元素之和相等.

N可以是最大20.K可以是最大8

问题是使用DP + Bitmasks专门解决!

我无法理解从哪里开始!由于有K套维护,我不能把K各自代表一些或另一个!

如果我尝试将整个集合作为状态而将K作为另一个,我在创建循环关系时遇到问题!

你能帮我吗？？

原始问题的链接问题

我觉得Kadane的算法是最大子数组问题的真正动态规划解决方案的修改版本。为什么我会这么觉得？我觉得是因为计算最大子数组的方法可以采用：

for(i=0;i<N;i++)
    {
        DP[i][A[i]]=true;
        for(j= -ve maximum ;j<= +ve maximum ;j++)
        if(DP[i-1][j])
            DP[i][j+A[i]]=true;
    }

递归是如果可以用一个以 i-1 个元素结尾的子数组来形成j，我可以使用第 i 个元素形成j+A[i]并且也可以通过在第 i 个位置开始一个子阵列来单独形成A[i]并且最后我们可以在这个 DP 数组中搜索标记为 true 的最大 j！

注意：DP[i][j]表示是否可以使用以 i 结尾的子数组来生成 j！在这里我假设 j 也可以是负数。！现在可以很容易地推导出 sum+ 一个负数 < sum 。这意味着添加任何负指数无助于获得更好的总和，这就是我们可以放弃它们的原因！Morover 我们关心直到i-1th 位置的最大 j并将它与i th 元素连接起来，这让我觉得这是一种贪婪的选择（只是因为最大值 + 元素给了我一个最大值）。

注意：我现在还没有研究过贪婪算法，但我知道什么是贪婪的选择！

编辑：有人说我的算法没有任何意义，所以我试图发布我的代码以使自己清楚。我没有把 j 当作 -ve，因为它们没有成果。我重复我的状态被定义为是否可以使用以 i 结尾的子数组来生成 j。

#include<bits/stdc++.h>
using namespace std;
int DP[101][101];
int main()
{
    int i,j,ans=INT_MIN;
    int …

编写一个程序，将网格的宽度、W 和高度 H 作为输入，并输出用 (2x1) 多米诺骨牌平铺 W×H 网格的不同方式的数量

我知道如何用 3 x N 网格解决问题，但是为此编写递归公式对我来说太难了！

我不知道该怎么做！

我创建了两个函数 F(n) - 平铺直到 N 的完整方法和 S(n) 用于 3 x N 的不完全平铺方法的数量！但这里由于高度是可变的我想不出任何东西

约束：(0 \xe2\x89\xa4 W+H \xe2\x89\xa4 22)

我试图在数组A中保存32位数字的二进制等价.为了测试我的showbits()函数,当我遇到这个东西时,我选择了8,9:

当我在函数showbits()中放置memset时,我在代码中面临一个不合理的事情,我正在考虑荒谬的整数,而我期望输出为

00000000000000000000000000001000

这是8的二进制等价物.当我将memset放在main()方法中时,它正常工作并给我正确的输出.我走出界限(我看不到它!).

我的代码: SHOWBITS:

void showbits(int A[32],int num)
{
    int k=0;
    memset(A,0,sizeof(A));
    while(num>0)
    {
        A[k] = num&1;
        k++;
        num>>=1;
    }
    return ;
}

注意:我已将memset放在showbits中,我得到的答案不正确! 主要:

int main()
{
    int A[32],i;
    showbits(A,8);
    for(i=31;i>=0;i--)
        printf("%d",A[i]);
    return 0;
}

整个测试程序:

#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
void showbits(int A[32],int num)
{
    int k=0;
    memset(A,0,sizeof(A));
    while(num>0)
    {
        A[k] = num&1;
        k++;
        num>>=1;
    }
    return ;
}
int main()
{
    int A[32],i;
    showbits(A,8);
    for(i=31;i>=0;i--)
        printf("%d",A[i]);
    return 0;
}

当我在showbits()之前将那个memset语句放在Main方法中时,我得到了正确的输出!

编辑 如果有人对我得到的东西感兴趣

398420075242008462686872420075219611920941961187434-2205336646196127610926869242 …

给定N个工作,其中每个工作由以下三个元素表示.

1)开始时间

2)完成时间.

3)利润或价值相关.

找到作业的最大利润子集,使子集中没有两个作业重叠.

我知道一个动态编程解决方案,其复杂度为O(N ^ 2)(接近LIS,我们必须检查以前的元素,我们可以合并当前间隔并采用合并给出最大值的区间直到第i个这个解决方案可以使用二进制搜索和简单排序进一步改进为O(N*log N)!

但是我的朋友告诉我,甚至可以通过使用Segment Trees和二分搜索来解决它!我不知道我将在哪里使用Segment Tree以及如何使用.

你能帮我吗？

根据要求,抱歉没有评论

我正在做的是根据起始索引进行排序,通过合并先前的时间间隔和它们的最大可获得值,将最大可获得值存储到DP [i]中i!

 void solve()
    {
        int n,i,j,k,high;
        scanf("%d",&n);
        pair < pair < int ,int>, int > arr[n+1];// first pair represents l,r and int alone shows cost
        int dp[n+1]; 
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            scanf("%d%d%d",&arr[i].first.first,&arr[i].first.second,&arr[i].second);
        std::sort(arr,arr+n); // by default sorting on the basis of starting index
        for(i=0;i<n;i++)
        {
            high=arr[i].second;
            for(j=0;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
            {
                if(arr[i].first.first>=arr[j].first.second)  
                        high=std::max(high …