2016级算法期末模拟练习赛-D.AlvinZH的序列问题
1111 AlvinZH的序列问题
思路
中等题，动态规划。
简化题意，。
坑点一：二维int数组MLE，明显会超过内存限制，由于\(n\)最大为1e4，那么我们的dp数组最大也是1e4，考虑使用short int。
坑点而：被题目开始的子序列描述误导，题目没有要求等差数列中数字顺序和输入顺序一致，所以可以先将数组排序。
dp[i][j]：以A[i]、A[j]开头的等差数列（可保证i<j）。初始化值为2。
状态转移：固定j，i与k分别向两边扩展，当2*A[j]=A[i]+A[k]时，说明A[i]、A[j]、A[k]可以组成等差数列。则有：dp[i][j]=dp[j][k]+1。
分析
这个DP也很有意思哦，固定一维，向两边扩展，真是妙啊！
时间复杂度：接近\(O(n^2)\)。
参考代码
//
// Created by AlvinZH on 2017/11/27.
// Copyright (c) AlvinZH. All rights reserved.
//
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MaxSize 10005
using namespace std;
int n, ans;
int A[MaxSize];
short int dp[MaxSize][MaxSize];
int main()
{
while(~scanf("%d", &n))
{
for (int i = 0; i < n; ++i)
scanf("%d", &A[i]);
sort(A, A+n);
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
dp[i][j] = 2;
ans = 2;
for (int j = n-2; j > 0; --j) {
int i = j-1, k = j+1;
while(i>=0 && k<n)
{
if(A[i]+A[k] < 2*A[j])
k++;
else if(A[i]+A[k] > 2*A[j])
i--;
else
{
dp[i][j] = dp[j][k] + 1;
if(dp[i][j] > ans)
ans = dp[i][j];
i--, k++;
}
}
}
printf("%d\n", ans);
}
}1、iOS开发：关于UIView的autoresizingMask属性
2、由一段代码说开去——sscanf与string
3、11月份是个少产的季节
4、IEF could not decode Chinese character in IE history well
5、如何提升开发效率-前端技术选型篇