POJ1017希尔排序

POJ1017是一个关于希尔排序的问题。希尔排序是一种插入排序的变种，也称为缩小增量排序。其基本思想是将待排序的数组按照一定的增量分成若干子序列，分别对这些子序列进行插入排序。随后，逐渐减小增量，继续按照此方法排序，直至增量为1，即对整个数组进行插入排序。

具体来说，希尔排序可以通过以下步骤实现：
1. 选择一个增量序列t1, t2, …, tk, 其中ti>tj, tk=1；
2. 按增量序列个数k，对序列进行k趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列；
4. 分别对各子表进行插入排序；
5. 合并各子序列，得到完整的有序序列。

希尔排序是一种高效的排序算法，其时间复杂度取决于所选取的增量序列。通常来说，增量序列可以选择使用Knuth提出的增量序列：1, 4, 13, 40, …，时间复杂度为O(N^(3/2))。

相关问题

poj Divisibility

POJ Divisibility是一个编程题，要求编写一个程序来确定一系列整数是否可被K整除。输入文件的第一行包含两个整数N和K，用一个空格分隔。第二行包含一系列N个整数，以空格分隔。每个整数的绝对值不大于10000。在输出文件中，如果给定的整数序列可被K整除，则写入单词“Divisible”，否则写入“Not divisible”。

该问题的解决方法可以使用动态规划来实现。我们可以使用一个二维数组dp来记录前i个数产生的余数情况。具体操作如下：
- 初始化dp为1，表示前0个数产生的余数为0。
- 对于每个数a[i]，遍历0到K-1的余数j，如果前i-1个数可以产生余数j，则更新dp[i][(j+a[i])%K]和dp[i][(j-a[i])%K]为1。
- 最后判断dp[N]是否为1，如果是，则输出“Divisible”，否则输出“Not divisible”。

举个例子，对于序列17, 5, -21, 15，根据题目中的描述，可以通过添加加号和减号来得到不同的算术表达式，如17+5-21+15=16，17+5-21-15=-14等。在这个例子中，序列是可被7整除的，因为存在一个算术表达式17+5-21-15=-14的结果可以被7整除，但不可被5整除。

因此，根据题目的描述和动态规划的思想，我们可以编写一个程序来解决POJ Divisibility问题。

POJ1159

POJ1159是一个动态规划问题，也被称为“Palindrome”。题目描述如下：

给定一个字符串，你需要将它分割成若干个子串，使得每个子串都是回文串。求最少需要分割几次。

例如，对于字符串“abcbm”，最少需要分割一次，将它分割成“a”、“bcb”和“m”三个回文子串。

解题思路：

使用动态规划求解。定义dp[i]为字符串s的前i个字符最少需要分割几次才能满足条件。则有如下状态转移方程：

dp[i] = min(dp[j]) + 1，其中j<i且s[j+1:i]是回文串

即在前i个字符中找到一个位置j，使得s[j+1:i]是回文串，且dp[j]是前j个字符最少需要分割几次才能满足条件，那么dp[i]就可以通过dp[j]得到。

时间复杂度为O(n^2)。具体实现细节见下面的代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int n;
char s[N];
int dp[N];

bool check(int l, int r)
{
    while (l < r)
    {
        if (s[l] != s[r])
            return false;
        l++;
        r--;
    }
    return true;
}

int main()
{
    cin >> n >> s + 1;

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (check(j + 1, i))
                dp[i] = min(dp[i], dp[j] + 1);

    cout << dp[n] - 1 << endl;

    return 0;
}