我不想当烟花般灿烂的瞬间，只想当你普通的永远。

试着在Linux下编译并运行程序。。。

结果Linux死活装不上qwq，然后就拷贝了慎老师的虚拟机文件。

以后就尽量使用Linux写代码了，提前适应环境。

今天用了大半天联系Linux基本操作，好不容易终于写出了一道题。

记录一下常用Linux命令（虽然我从来没用过但是凭感觉就能写出很多常用命令，感觉Linux还是挺不错的）：

修改vimrc配置：sudo vim ~/.vimrc（比较好看的字体：Tlwg typo medium）
查看当前目录：ls
切换目录：cd
运行程序：./xxx
vim编译NOI Linux下可以直接F9 ，当然也可以：g++ xx -o xx -Wall

现在唯一严重的问题是我不知道为什么复制粘贴没法使用，Vim内部粘贴很好用，但是从Vim复制到命令行什么的就不行，到时候再试试。

写了道不难的题，一开始算错了表达式结果还写了暴力。。

5131 求和2015

一条狭长的纸带被均匀划分出了 n 个格子，格子编号从 1 到 n。每个格子上都染了一种颜色colori（用[1，m]当中的一个整数表示），并且写了一个数字number
定义一种特殊的三元组：(x, y, z)，其中 x，y，z 都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：
\1. x, y, z都是整数,x <y <z,y−x=z−y
\2. colorx= colorz
满足上述条件的三元组的分数规定为(x + z) ∗ (numberx+ numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 10,007 所得的余数即可。

输入描述 Input Description

第一行是用一个空格隔开的两个正整数n和m，n代表纸带上格子的个数，m代表纸带上颜色的种类数。
第二行有n个用空格隔开的正整数，第i个数字numberi代表纸带上编号为i的格子上面写的数字。
第三行有n个用空格隔开的正整数，第i个数字colori代表纸带上编号为i的格子染的颜色。

输出描述 Output Description

共一行，一个整数，表示所求的纸带分数除以 10,007 所得的余数。

样例输入 Sample Input

输入样例1

6 2

5 5 3 2 2 2

2 2 1 1 2 1

输入样例2

15 4

5 10 8 2 2 2 9 9 7 7 5 6 4 2 4

2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

样例输出 Sample Output

输出样例1

输出样例2

1388

数据范围及提示 Data Size & Hint

【输入输出样例 1 说明】

纸带如题目描述中的图所示。
所有满足条件的三元组为：(1,3,5),(4,5,6)。
所以纸带的分数为(1 + 5) ∗ (5 + 2) + (4 + 6) ∗ (2 + 2) = 42 + 40 = 82。
【数据说明】
对于第 1 组至第 2 组数据，1 ≤ n ≤ 100,1 ≤ m ≤ 5；
对于第 3 组至第 4 组数据，1 ≤ n ≤ 3000,1 ≤ m ≤ 100；
对于第 5 组至第 6 组数据，1 ≤ n ≤ 100000,1 ≤ m ≤ 100000，且不存在出现次数超过 20 的颜色；
对于全部 10 组数据， 1 ≤ n ≤ 100000,1 ≤m ≤ 100000,1 ≤ colori≤ m,1 ≤numberi≤ 100000。

题解

显然只有同奇同偶的数对中间才能存在y

然后我们把题目中的计算表达式乘开，并且考虑对当前位置能否快速统计和前面的数构成二元组对答案的贡献。

$\sum_{y}(x + y)(V_x+V_y) = kxV_x + x\sum{V_y} + \sum_{y}*V_x+\sum{yV_y}$

我们需要维护的量也很清楚了，用三个数组每次保存当前按下标奇偶性分类的相同颜色的（就是桶）三个和式。

时间复杂度

$O(n)$

Code:

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define ll long long
#define mod 10007
ll f[2][maxn] , g[2][maxn] , ans , ct[2][maxn] , h[2][maxn];
int v[maxn] , c[maxn] , n , m;
int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&v[i]);
	for(int i = 1 ; i <= n ;++i)
		scanf("%d",&c[i]);
	for(int i = 1 ; i <= n ; ++i)
	{
		ans += 1ll*ct[i&1][c[i]] * i * v[i] + 1ll*i * f[i&1][c[i]] + 1ll*v[i] * g[i&1][c[i]] % mod + 1ll*h[i&1][c[i]];
		ans %= mod;
		f[i&1][c[i]] += v[i];
		g[i&1][c[i]] += i;
		h[i&1][c[i]] += 1ll * i * v[i];
		f[i&1][c[i]] %= mod , g[i&1][c[i]] %= mod , h[i&1][c[i]] %= mod;
		ct[i&1][c[i]] ++;
	}
	printf("%lld",ans);
}

数据包的调度机制

总时间限制:

1000ms
内存限制:

65536kB
描述
随着 Internet的迅猛发展,多媒体技术和电子商务应用日益广泛,Internet上的服务质量(QoS,Qualityof Service)问题已越来越受到重视。网络中采用的数据包调度机制与网络的服务质量 QoS 有着密切的关系。研究表明传统的基于队列的调度机制已不能满足网络服务质量QoS 的需求。服务质量 QoS 取决于数据包的延迟。每一个数据包都有一个延迟惩罚值。由于数据包承载的数据不同,不同数据包的延迟惩罚值也可能不同。此外,数据包的延迟也和它的发送顺序有关。如果一个数据包被第K个发送,假设它的延迟惩罚值是D,则这个数据包的最终延迟是 (K - 1) * D。北京大学2012 级信息学院的同学在程序设计课堂上,设计了一种新的基于栈的数据包的调度算法。同学们通过栈的先进后出(Last in First out)的原理,改变数据包的发送顺序,以减小数据包的延迟总值。给定N 个等待调度的数据包,起始这N 个数据包排成一个队列等待发送。接着,这些数据包按序进栈,调度算法可以控制数据包的出栈顺序。因此通过栈,可以将后面的数据包先于前面的数据包发送出去。请你实现一个调度算法使N 个数据包的延迟总值最小。
输入

标准的输入包含若干组测试数据。输入第一行是整数T(1 <= T <= 1000)，表明有T组测试数据。紧接着有T组连续的测试。每一组测试数据的第1行是 N（N <= 100）,表述数据包的个数。接着的 N 行,每一行是一个整数,第i 行表示数据包i的延迟惩罚值( <=50 )。
输出

对于每组测试数据，输出最小的延迟总值。
样例输入
1 5 5 4 3 2 2
样例输出
24

题解

可以想到这是一个

$O(n^3)$

的dp

然后我们可以猜是区间dp。

。。。好菜啊，一道dp都不会

我们考虑枚举一个区间最后出去的那个元素，然后这种情况必定是左边先全出去，然后右边都出去，最后是它自己（但是这种东西好难想啊，最优子结构也不会证啊。。)

但是就是可以区间dp啊。。

Code：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 155
int f[maxn][maxn] , n , v[maxn] , s[maxn];
int main()
{
	int t;
	scanf("%d",&t);
	while(~(--t))
	{
		scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&v[i]);
	for(int i = 1 ; i <= n ; ++i)
		s[i] = s[i-1] + v[i];
	std::memset(f,0,sizeof(f));
	for(int len = 2 ; len <= n ; ++len)
		for(int fr = 1 , to ; (to = fr + len - 1) <= n ; ++fr)
		{
			f[fr][to] = 0x7ffff;
			for(int k = fr ; k <= to ; ++k)
				f[fr][to] = std::min(f[fr][to] , f[fr][k-1] + f[k+1][to] + v[k] * (len-1) + (s[to]-s[k])*(k-fr));
		}
	printf("%d\n",f[1][n]);
	}
}