poj1699 best sequence
时间: 2023-05-01 16:04:27 浏览: 88
这是一道算法题,需要对给定的数列进行操作,使得操作后的数列的最大值最小。具体做法是使用二分查找,找到一个最小的值mid,使得能够通过一些操作将数列中的每个数都变为不大于mid的数。然后再验证是否存在这样一种操作方案能够实现这个目标。具体实现可以参考相关的算法教材或者网上的题解。
相关问题
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)。具体实现细节见下面的代码:
```c++
#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;
}
```