C
对于一个等差数列，它里面包含的等差数列（取这个数列的第i位~第j位），必定也是等差数列。
寻找等差数列的时候，如果一个等差数列，向最左/最右加1个数后，仍是等差数列，则把它们加上。从而寻找所有场上的等差数列，必定是不重叠的，等差数列彼此独立。
从而可以从1遍历到n，O(n)复杂度。
对于每一段等差数列，只统计里面包含的长度大于等于2的等差数列。最后再加上长度等于1的等差数列，即为单独的每个数，为n。这样，思路会清晰一点
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define ULL unsigned long long
5
6 const LL mod_1=1e9+7;
7 const LL mod_2=998244353;
8
9 const double eps_1=1e-5;
10 const double eps_2=1e-10;
11
12 const int maxn=2e5+10;
13
14 LL a[maxn];
15
16 int main()
17 {
18 LL n,i,j,d;
19 LL sum=0;
20 cin>>n;
21 for (i=1;i<=n;i++)
22 cin>>a[i];
23 j=1;
24 for (i=1;i<n;)
25 {
26 d=a[i+1]-a[i];
27 j=i;
28 i++;
29 while (i<n && a[i+1]-a[i]==d)
30 i++;
31 sum+=1LL*(i-j)*(i-j+1)/2;
32 }
33 cout<<sum+n;
34
35 return 0;
36 }
D
DP
写成数组形式，好理解一点，写少一点代码
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define ULL unsigned long long
5
6 const LL mod_1=1e9+7;
7 const LL mod_2=998244353;
8
9 const double eps_1=1e-5;
10 const double eps_2=1e-10;
11
12 const int maxn=2e5+10;
13
14 LL f[maxn][2];
15
16
17 int main()
18 {
19 LL n,i,a;
20 f[0][0] = 0;
21 f[0][1] = -1e18;
22 cin>>n;
23 for (i=1;i<=n;i++)
24 {
25 cin>>a;
26 f[i][0] = max(f[i-1][0], f[i-1][1] + a*2);
27 f[i][1] = max(f[i-1][1], f[i-1][0] + a);
28 }
29
30 cout<<max(f[n][0],f[n][1]);
31 return 0;
32 }
E
floyd 求两两每个点之间的距离 + dfs获得几个桥所有可能的顺序
看到别人有用next_permutation，而且是挺多人用这个，挺不错。
但是后面，直接一行写出情况，对于大部分人来说是不是容易写错？而且关键是挺多人都这样写，我感觉比较神奇emmm。我个人，感觉用dfs相对不容易写错。
dfs获得几个桥所有可能的顺序，其实就很像旅行商问题，所有城市都访问一遍。然后这里是桥可以选择两个方向，也不好用状态压缩。
g个点，2^g个方向，桥的顺序，g!排列组合，每种桥方向类型，g个权值和相加，O(2^g*g!*g) 19,200 再乘个Q，没问题
我在比赛的时候，把floyd的顺序搞反了，然后几天找不到问题，真的绷不住了！！！floyd算法，三重循环的顺序问题，不要写错了 - congmingyige - 博客园 (cnblogs.com)
1 /*
2 n,m的大小，对应创建数组的大小，不要弄混，特别是这类题，n<=400，m<=2e5，提交前要检查一遍。当RE的时候，就要第一时间意识到数组大小设置错误的问题
3
4 怎么也调不出问题，包括检查代码，造样例，看题面，就立刻先切换到下一题。没必要花那么多时间耗在上面，否则检查错误，采用错误的方法，做很多无用功。而且影响做题时间和效率。这些时间，今早做下一题，有可能就做出来其它题了
5 做选择，要么全攻下一题（意识到难发现错误在哪，立刻切换，检查时间不要太长），要么剩下这些时间，全力检查这一题，不要既这又那
6 用assert等方式找一下问题所在，还有造一下大样例
7 */
8 #include <bits/stdc++.h>
9 using namespace std;
10 #define LL long long
11 #define ULL unsigned long long
12
13 const LL mod_1=1e9+7;
14 const LL mod_2=998244353;
15
16 const double eps_1=1e-5;
17 const double eps_2=1e-10;
18
19 const int maxn=4e2+10;
20 const int maxm=2e5+10;
21
22 LL u[maxm],v[maxm],t[maxm],dist[maxn][maxn],b[10],g,n,result;
23 bool vis[10];
24
25 void dfs(LL d, LL ans, LL road)
26 {
27 LL i,j;
28 if (ans==g)
29 {
30 result = min(result, road+dist[d][n]);
31 return;
32 }
33 for (i=1;i<=g;i++)
34 if (vis[i]==0)
35 {
36 j=b[i];
37
38 vis[i]=1;
39 dfs(v[j], ans+1, road+dist[d][u[j]] + t[j]);
40 vis[i]=0;
41
42 vis[i]=1;
43 dfs(u[j], ans+1, road+dist[d][v[j]] + t[j]);
44 vis[i]=0;
45 }
46 }
47
48 int main()
49 {
50 LL m,q,i,j,k;
51 cin>>n>>m;
52 for (i=1;i<=n;i++)
53 for (j=1;j<=n;j++)
54 dist[i][j] = 1e15;
55 for (i=1;i<=n;i++)
56 dist[i][i]=0;
57 for (i=1;i<=m;i++)
58 {
59 cin>>u[i]>>v[i]>>t[i];
60 dist[ u[i] ][ v[i] ] = dist[ v[i] ][ u[i] ] = min(dist[ u[i] ][ v[i] ], t[i]);
61 }
62
63 for (k=1;k<=n;k++)
64 for (i=1;i<=n;i++)
65 for (j=1;j<=n;j++)
66 dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
67 /*
68 for (i=1;i<=n;i++)
69 for (j=1;j<=n;j++)
70 assert(dist[i][j]<1e15);
71 */
72
73 cin>>q;
74 while (q--)
75 {
76 cin>>g;
77 for (i=1;i<=g;i++)
78 cin>>b[i];
79 memset(vis,0,sizeof(vis));
80 result=1e18;
81 dfs(1,0,0);
82 //assert(result<1e18);
83 cout<<result<<endl;
84 }
85
86 return 0;
87 }
88 /*
89 g个点
90 2^g个方向，桥的顺序，g!排列组合，每种桥方向类型，g个权值和相加，O(2^g*g!*g) 19,200 再乘个Q，没问题
91 */
F
应该看一下题面，在剩余1个小时的时候，这样才有时间做和取舍（题D、E) 这种属于题面很容易理解，也很容易想到解法的。就是写的过程中容易写错，debug也是，需要时间长一点 感觉这是高手和某类菜鸟的区别。某类菜鸟也可以很快找到解法，就是写代码和调试代码的时候，对于这类比较琐碎的代码，需要写挺久
能想到的基础题目是用DP做，二维方格，dp[i][j]=max(dp[i-1][j], dp[i][j-1])。
现在是n、m相乘比较大，然后硬币数比较少。
因为只能向下或者向右，所以对于一个点，只有列的数值小于等于它的点，才能访问到它。这容易想到树状数组。同样，对于行，也是只有行的数值小于等于它的点，才能访问到它。
f[i]= max(f[j]) + 1。 i表示这个点的列数值为i，j是所有小于i的数，用树状数组获取f数组里1~i的最大值。
按照硬币行数值优先，然后列数值优先的顺序排序，然后依次访问硬币。可以确保，对于该硬币，前面的硬币的行都是小于等于它，后面的硬币的行都是大于它，或者行等于它但是列大于它，无法从后面的硬币到该硬币。
1 /*
2 应该看一下题面，在剩余1个小时的时候，这样才有时间做和取舍（题D、E)
3 这种属于题面很容易理解，也很容易想到解法的。就是写的过程中容易写错，debug也是，需要时间长一点
4 感觉这是高手和某类菜鸟的区别。某类菜鸟也可以很快找到解法，就是写代码和调试代码的时候，对于这类比较琐碎的代码，需要写挺久
5
6 用xpre,ypre,x,y，这样变量不容易搞错。还有，找问题的，多检查一下变量，这种变量最容易写错
7 */
8 #include <bits/stdc++.h>
9 using namespace std;
10 #define LL long long
11 #define ULL unsigned long long
12
13 const LL mod_1=1e9+7;
14 const LL mod_2=998244353;
15
16 const double eps_1=1e-5;
17 const double eps_2=1e-10;
18
19 const int maxn=2e5+10;
20
21 pair<int,int> par[maxn];
22
23 map<pair<int,int>, pair<int,int> > mp;
24
25 pair<int, int> pre[maxn];
26 int f[maxn];
27 vector<string> vec;
28
29 void add_path(pair<int,int> dpre, pair<int,int> d)
30 {
31 int i,j;
32 string str="";
33 for (i=dpre.first;i<d.first;i++)
34 str+='D';
35 for (j=dpre.second;j<d.second;j++)
36 str+='R';
37 vec.push_back(str);
38 }
39
40 void dfs(pair<int,int> d)
41 {
42 pair<int,int> dpre;
43
44 dpre = mp[d];
45
46 if (dpre!=make_pair(-1,-1))
47 {
48 add_path(dpre,d);
49 dfs(dpre);
50 }
51 else
52 add_path(make_pair(1,1),d);
53 }
54
55 int main()
56 {
57 int h,w,n,x,y,v,i,j,y_max=2e5;
58 pair<int,int> dpre,d;
59 cin>>h>>w>>n;
60 memset(f,0,sizeof(f));
61 for (i=0;i<n;i++)
62 {
63 cin>>x>>y;
64 par[i] = make_pair(x,y);
65 }
66 sort(par, par+n);
67
68 for (j=0;j<n;j++)
69 {
70 x = par[j].first;
71 y = par[j].second;
72 dpre = make_pair(-1,-1);
73
74 v = 0;
75 for (i=y;i>=1;i-=i&-i)
76 if (f[i]>v)
77 {
78 v=f[i];
79 dpre = pre[i];
80 }
81
82 v++;
83
84 if (v>f[y])
85 {
86 d = make_pair(x,y);
87 mp[d] = dpre;
88
89 for (i=y;i<=y_max;i+=i&-i)
90 if (v>f[i])
91 {
92 f[i]=v;
93 pre[i]=d;
94 }
95 }
96 }
97
98 v=0;
99 for (i=y_max;i>=1;i-=i&-i)
100 if (f[i]>v)
101 {
102 v=f[i];
103 dpre=pre[i];
104 }
105 cout<<v<<endl;
106 add_path(dpre,make_pair(h,w));
107 dfs(dpre);
108 reverse(vec.begin(), vec.end());
109 for (auto d:vec)
110 cout<<d;
111
112 return 0;
113 }
学习官方代码，
vector 初始化，第二个数，就是vector里初始化的数值
LIS，二分的写法，4行就搞定了？？！！！
对于pre数组，记录点id，而不是记录二维坐标，这样方便一点，写少一点代码
用二分的写法，而不是树状数组的写法，只用修改一次pre，这个点的pre就是数组里上一个点，用树状数组，每次+lowbit后，都要判断修改一次，总感觉代码量相对比较大，不利索
pre[i] = (it ? id[it - 1] : -1); 这个写法不错
官方也是用while、vector记录从终点出发，不断pre的点序列，然后用reverse，的确，这个好用。我感觉用dfs，写得挺不舒服的
1 int now = id[m];
2 while (now != -1) {
3 path.push_back(coins[now]);
4 now = pre[now];
5 }
6 path.emplace_back(1, 1);
7 reverse(path.begin(), path.end());
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 int main() {
6 int h, w, n;
7 cin >> h >> w >> n;
8 vector<pair<int, int>> coins;
9 for (int i = 0; i < n; i++) {
10 int r, c;
11 cin >> r >> c;
12 coins.emplace_back(r, c);
13 }
14 sort(coins.begin(), coins.end());
15 vector<int> dp(n, 1e9), id(n, -1), pre(n);
16 for (int i = 0; i < n; i++) {
17 int it = upper_bound(dp.begin(), dp.end(), coins[i].second) - dp.begin();
18 dp[it] = coins[i].second;
19 id[it] = i;
20 pre[i] = (it ? id[it - 1] : -1);
21 }
22 int m = n - 1;
23 while (id[m] == -1) --m;
24 vector<pair<int, int>> path = {{h, w}};
25 int now = id[m];
26 while (now != -1) {
27 path.push_back(coins[now]);
28 now = pre[now];
29 }
30 path.emplace_back(1, 1);
31 reverse(path.begin(), path.end());
32 string s;
33 for (int i = 0; i < (int) path.size() - 1; i++) {
34 int d = path[i + 1].first - path[i].first;
35 int r = path[i + 1].second - path[i].second;
36 while (d--) s.push_back('D');
37 while (r--) s.push_back('R');
38 }
39 cout << m + 1 << '\n' << s << '\n';
40 }
G
可以用，DP，f[i][j]。对于以i为根的子树，现在已经选取了j个点，但是这么多子树，j这么大，DP会超时的。
记录点1到某个点的长度，从大到小排序依次取
取了一个点后，点1到这个点经过的边，所有的边值都要变为0，即点1到其它点经过的边中，再用到这些边，也无法增加权值。
标签：10,const,int,LL,long,ABC369,path From： https://www.cnblogs.com/cmyg/p/18398916