信息学奥赛一本通（c++）题号：2066

### 回答1：
题目描述：编写一个C++程序，输入一个整数n，输出对应的n行数字

解题思路：使用循环语句for或while，循环从1到n输出对应数字，使用换行符

代码示例：

#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
cout << i << endl;
}
return 0;
}

### 回答2：
题目描述：给定一个字符串S和一个整数n，你需要将S分为若干个子串，使每个子串的长度不超过n，且相邻的两个子串中，后一个子串的第一个字符和前一个子串的最后一个字符相同。求符合要求的最多子串数量。

这个题目可以用动态规划来解决。我们定义一个二维数组dp，其中dp[i][j]表示将S的前i个字符分成若干个子串，而第j个子串的最后一个字符为S[i]时，可以得到的最大子串数量。

那么怎么计算dp[i][j]呢？如果我们知道了dp[i-1][k]，那么我们可以考虑将最后一个子串扩展到S[i]。此时最后一个子串的长度是i-k，如果这个长度小于等于n，那么我们可以将最后一个子串扩展到S[i]，即dp[i][j]=dp[i-1][k]+1。但是这个条件并不够，因为题目要求相邻的两个子串中，后一个子串的第一个字符和前一个子串的最后一个字符相同，所以我们还需要满足S[i-(i-k)][i-k+1]等于S[i]，即S[i-(i-k)]表示前一个子串的最后一个字符，等于S[i]，表示后一个子串的第一个字符。因此，如果满足这个条件，我们可以将最后一个子串扩展到S[i]，即dp[i][j]=dp[i-1][k]+1。

对于这个问题，我们可以枚举所有的i和j，遍历所有的k，计算每个dp[i][j]的值，最后取所有的dp[i][j]中的最大值就是我们要求的答案。

时间复杂度是O(n^3)，空间复杂度是O(n^2)。如果n很大，可以考虑压缩状态，将dp数组中的所有子串看作一个整体，用一个三维数组表示状态。

### 回答3：
题目描述：给定一个长度为n（n<=1000）的序列a_i（1<=i<=n），你需要求出这个序列中最长的不下降子序列的长度。

解题思路：可以用dp的方式解决这个题目，定义dp[i]为以第i个数结尾的最长不下降子序列的长度，那么自然有：

dp[i]=max(dp[j])+1(0<j<i,a[j]<=a[i])

其中a[j]<=a[i]表示a[i]是从a[j]转移来的，那么dp[i]就是将前面的最长不下降子序列加上当前的数后得到的结果，取最大值即可。最后我们只需要遍历dp数组，取得其中的最大值即为所求的最长不下降子序列的长度。

时间复杂度分析：该算法至少需要O(n^2)的时间复杂度，因为需要计算每一个dp[i]的值。实际上由于dp[i]只依赖于前面的dp[j](0<j<i)，所以可以通过线段树或者树状数组优化，将时间复杂度优化到O(nlogn)。

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
int a[MAXN],dp[MAXN];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
dp[i]=1; //初始化dp数组
}
for(int i=1;i<=n;i++){ //i从1到n枚举每个数字
for(int j=1;j<i;j++){//j从1到i-1枚举i之前的每个数字
if(a[j]<=a[i]){//如果前面有小于等于当前的数字，则可以从其转移而来
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int ans=0;
for(int i=1;i<=n;i++){//找到dp数组中的最大值
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
return 0;
}