poj3278-分支限界法

POJ3278是一道分支限界法的经典问题，题目描述为：

给定两个整数N和K，有两种操作：

1.将N加1或减1，代价为1。

2.将N乘2，代价为0。

问将N变为K的最小代价是多少。

这道题可以使用分支限界法来求解。我们可以使用一个队列来存储当前状态，每次取出队头元素，进行扩展操作，将扩展出的新状态加入队列中。在扩展操作时，我们需要注意一些剪枝策略，比如：

1.如果当前状态的代价已经大于之前的最小代价，就不需要再扩展该状态。

2.如果当前状态已经出现过了，也不需要再扩展该状态。

3.如果当前状态的N已经超过K，也不需要再扩展该状态。

这些剪枝策略可以有效地减少状态的扩展次数，提高算法效率。

下面是使用C++实现的代码：

相关问题

POJ - 1661

根据提供的引用内容，这个问题讨论的是POJ-1661题，这是一个dp问题。题目给定了一系列平台的高度和人的起始位置，要求从起始位置跳到地面的最短时间。通过设置状态dp[i]表示从第i个平台的左边跳到地面所需的最小时间，dp[i]表示从第i个平台的右边跳到地面所需的最小时间，然后分别计算左右走所需的最小时间，最后取左右走中的较小值作为结果。

POJ - 3616

POJ - 3616是一个题目，题目描述如下：

给定一组区间，每个区间有一个权重，要求选择一些区间，使得这些区间的右端点都小于等于k，并且权重之和最大。请问最大的权重和是多少？

解决这个问题的思路是使用动态规划。首先，将区间按照左端点从小到大进行排序。然后，定义一个dp数组，dp[i]表示右端点小于等于i的所有区间所能得到的最大权重。

接下来，遍历每一个区间，对于每个区间i，将dp[i]初始化为区间i的权重。然后，再遍历i之前的每个区间j，如果区间j的右端点小于等于k，并且区间j的权重加上区间i的权重大于dp[i]，则更新dp[i]为dp[j]加上区间i的权重。

最后，遍历整个dp数组，找到最大的权重和，即为所求的答案。

下面是具体的代码实现：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct interval{
    int start, end, weight;
};

interval intervals[10005];
int dp[10005];
int n, m, k;

bool compare(interval a, interval b) {
    if (a.start == b.start) {
        return a.end < b.end;
    } else {
        return a.start < b.start;
    }
}

int main() {
    while(~scanf("%d %d %d", &n, &m, &k)) {
        memset(dp, 0, sizeof dp);
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &intervals[i].start, &intervals[i].end, &intervals[i].weight);
        }
        
        sort(intervals, intervals + m, compare);
        
        for (int i = 0; i < m; i++) {
            dp[i] = intervals[i].weight;
            
            for (int j = 0; j < i; j++) {
                if (intervals[j].end <= k && dp[j] + intervals[i].weight > dp[i]) {
                    dp[i] = dp[j] + intervals[i].weight;
                }
            }
        }
        
        int maxWeight = 0;
        for (int i = 0; i < m; i++) {
            maxWeight = max(maxWeight, dp[i]);
        }
        
        printf("%d\n", maxWeight);
    }
}