AtCoder Beginner Contest 237 VP补题

E

大意：
给定一张无向图，两点间的边权：

较高点到较低点的边权等于高度差

较低点到较高点的边权等于高度差的负二倍

求：图中的最大dis值

思路：
按题意建边即可；

但是有负权，所以一般的dij不行。

赛后又加强过数据，所以我跑了spfa，T烂了。。。（但是我看有一个哥们还真用spfa冲过去了。。。【崩溃】）

官方题解的思路是dij

考虑“势”的思想（绝）：

对数据进行预处理，高点到低点的边权等于0，低点到高点的距离等于高度差（>=0)

那么就全是非负权边了。

跑完dij后只要把数据还原回去就可以了，dis[i]=h[i]-h[1]+dist[i]

code:

再说

F

大意：

求长度为 n，每个元素不大于m的序列，满足以下条件的有多少种：
最长上升子序列长度恰好为3.

思路：
m很小，只有10，那么久很容易想到暴力枚举+dp

不妨设i代表当前枚举到的数列长度，k1 表示当前序列长度为1的LIS的最后一个元素的最小值，k2 表示当前序列长度为2的LIS的最后一个元素的最小值，k3 则表示当前序列长度为3的LIS的最后一个元素的最小值

那么dp[i][k1][k2][k3]就代表对应情况的方案数。

那么每次再多枚举一个x，对x的大小进行分类讨论即可。

细节见code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1005;
const ll mod=998244353;
ll dp[N][12][12][12];
ll n,m;
int main()
{
	cin>>n>>m;
	dp[0][m+1][m+1][m+1]=1;
	for(int i=1;i<=n;++i)
	{
		for(int k1=1;k1<=m+1;++k1)
		{
			for(int k2=1;k2<=m+1;++k2)
			{
				for(int k3=1;k3<=m+1;++k3)
				{
					for(int x=1;x<=m;++x)
					{
						if(x<=k1) dp[i][x][k2][k3]=(dp[i-1][k1][k2][k3]+dp[i][x][k2][k3])%mod;
						else if(x<=k2) dp[i][k1][x][k3]=(dp[i-1][k1][k2][k3]+dp[i][k1][x][k3])%mod;
						else if(x<=k3) dp[i][k1][k2][x]=(dp[i-1][k1][k2][k3]+dp[i][k1][k2][x])%mod;
					}
				}
			}
		}
	}
	ll ans=0;
	for(int k1=1;k1<=m;++k1)
	{
		for(int k2=1;k2<=m;++k2)
		{
			for(int k3=1;k3<=m;++k3)
			{
			//	cout<<dp[n][k1][k2][k3];
				ans=(ans+dp[n][k1][k2][k3])%mod;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
 }