首页 > 代码库 > BZOJ 3357: [Usaco2004]等差数列
BZOJ 3357: [Usaco2004]等差数列
3357: [Usaco2004]等差数列
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 338 Solved: 160
[Submit][Status][Discuss]
Description
约翰发现奶牛经常排成等差数列的号码．他看到五头牛排成这样的序号：“1，4，3，5，7”
很容易看出“1，3，5，7”是等差数列．
给出N(1≤N≤2000)数字AI..AN(O≤Ai≤10^9)，找出最长的等差数列，输出长度．
Input
第1行：一个整数N.
第2到N+1行：每行一个整数Ai，表示牛的号码．
Output
最长等差数列的长度．
Sample Input
5
1
4
3
5
7
1
4
3
5
7
Sample Output
4
HINT
Source
Green
OTZ 美帝神题
本来想的是用SORT或HASH离散化所有的可能的公差，然后再分别跑个最长路，复杂度大概是$O(N^{2}log_{N})$或$O(N^{2})$的，然而好麻烦，不想写，(╯▔皿▔)╯
后来看到大家标的tag都是DP，动态规划之类的，想到可以直接在DP数组上做文章，看大多数懒人都是用的STL的map<int,int>勉强卡到9s，也有勤快人手写HASH表什么的。可惜BZOJ不支持C++14，不然有了unordered_map事情会简单很多。
写着写着就WA了，看看PoPoQQQ等大爷的题解才发现特殊处理蛮多的（起码有两处吧，2333~~~）。
1 #include <bits/stdc++.h> 2 3 const int mxn = 2005; 4 5 int n, ans, s[mxn]; 6 7 std::map<int, int> f[mxn]; 8 9 signed main(void)10 {11 scanf("%d", &n);12 13 if (n == 1)puts("1");14 else15 {16 for (int i = 1; i <= n; ++i)17 scanf("%d", s + i);18 19 for (int i = 1; i <= n; ++i)20 for (int j = 1; j < i; ++j)21 {22 using std::max;23 f[i][s[j]] = max(f[i][s[j]], 2);24 f[i][s[j]] = max(f[i][s[j]], f[j][(s[j] << 1) - s[i]] + 1);25 26 ans = max(ans, f[i][s[j]]);27 }28 29 printf("%d\n", ans);30 }31 }
@Author: YouSiki
BZOJ 3357: [Usaco2004]等差数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。