【题目】
题目描述：
有
n
n
n 条咸鱼，每条咸鱼都有自己的能力值
a
i
a_i
ai，现在你要给这些咸鱼送饭，当然咸鱼也有梦想，他们会暗中较劲，所以你给每个咸鱼送饭的时候要保证对于相邻的两条咸鱼，能力值大的咸鱼得到的饭要比咸鱼值少的多，请问最少送多少饭就能满足条件？
输入格式：
一开始是一个数字
t
t
t，表示数据组数
接下来
t
t
t 行，每行是一个数
n
n
n，表示咸鱼的数量
接下来一行有
n
n
n 个数，表示每个咸鱼的能力值
输出格式：
对于每组数据，输出答案
样例数据：
输入 2 3 1 2 3 4 3 1 2 2
输出 6 6
提示：
【样例解释】 第一个样例中第
1
1
1 个咸鱼送
1
1
1 份饭，第
2
2
2 个咸鱼送
2
2
2 份饭，第
3
3
3 个咸鱼送
3
3
3 份饭。
第二个样例中第
1
1
1 个咸鱼送
2
2
2 份饭，第
2
2
2 个咸鱼送
1
1
1 份饭，第
3
3
3 个咸鱼送
2
2
2 份饭，最后一个咸鱼送
1
1
1 份饭，因为最后两个咸鱼的能力值不是严格大于。
【数据范围】
30
%
30 \%
30% 的数据保证
t
t
t ≤
10
10
10，
n
n
n ≤
1000
1000
1000
100
%
100 \%
100% 的数据保证
t
t
t ≤
10
10
10，
n
n
n ≤
100000
100000
100000，
0
0
0 ≤
a
i
a_i
ai ≤
1
0
9
10^9
109
【分析】
其实也不是一道难题，只是有一个细节错了，就 Wa 了很久。。。
对于一个点
i
i
i，其实只用比较和
i
−
1
i-1
i−1 的关系就可以了（因为
i
i
i 和
i
+
1
i+1
i+1 的情况会在
i
+
1
i+1
i+1 的时候被算到）
比较的时候，
a
a
a 小的往大的连边，就表示能力大的要多吃点
记录
f
i
f_i
fi 表示
i
i
i 要多少饭，那么在拓扑排序的时候，直接更新就行了
【代码】
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std
;
int n
,t
,tot
;
int a
[N
],f
[N
],in
[N
];
int first
[N
],v
[N
],nxt
[N
];
void init()
{
tot
=0;
memset(f
,0,sizeof(f
));
memset(in
,0,sizeof(in
));
memset(first
,0,sizeof(first
));
}
void add(int x
,int y
)
{
tot
++;
nxt
[tot
]=first
[x
];
first
[x
]=tot
;
v
[tot
]=y
;
}
void Topology()
{
int x
,i
;
stack
<int>sta
;
for(i
=1;i
<=n
;++i
)
if(!in
[i
])
f
[i
]=1,sta
.push(i
);
while(!sta
.empty())
{
x
=sta
.top();sta
.pop();
for(i
=first
[x
];i
;i
=nxt
[i
])
{
in
[v
[i
]]--;
f
[v
[i
]]=max(f
[v
[i
]],f
[x
]+1);
if(!in
[v
[i
]]) sta
.push(v
[i
]);
}
}
}
int main()
{
int i
;
scanf("%d",&t
);
while(t
--)
{
init();
scanf("%d",&n
);
scanf("%d",&a
[1]);
for(i
=2;i
<=n
;++i
)
{
scanf("%d",&a
[i
]);
if(a
[i
]>a
[i
-1]) add(i
-1,i
),in
[i
]++;
if(a
[i
]<a
[i
-1]) add(i
,i
-1),in
[i
-1]++;
}
Topology();
long long ans
=0;
for(i
=1;i
<=n
;++i
)
ans
+=f
[i
];
printf("%lld\n",ans
);
}
return 0;
}
