Atcoder beginer contest 237 VP supplement

E

Carelessness ：
Given an undirected graph , The edge right between two points ：

The edge weight from the higher point to the lower point is equal to the height difference

The edge weight from the lower point to the higher point is equal to negative twice the height difference

seek ： Max in graph dis value

Ideas ：
Just build the edge according to the meaning of the topic ;

But it has negative power , So in general dij no way .

After the game, we strengthened the data , So I ran away spfa,T rotten ...（ But I think there is a buddy who really uses spfa Rushed over ...【 collapse 】）

The idea of the official solution is dij

consider “ potential ” Thought （ most ）：

Preprocess the data , The edge weight from high to low is equal to 0, The distance from low point to high point is equal to the height difference （>=0)

Then it's all non negative side .

Run away dij After that, just restore the data back ,dis[i]=h[i]-h[1]+dist[i]

code:

Besides,

F

Carelessness ：

Find the length of n, Each element is not greater than m Sequence , How many kinds of meet the following conditions ：
The length of the longest ascending subsequence is exactly 3.

Ideas ：
m Very small , Only 10, It's easy to think of violent enumeration for so long +dp

Might as well set i Represents the length of the current enumerated sequence ,k1 Indicates that the current sequence length is 1 Of LIS The minimum value of the last element of ,k2 Indicates that the current sequence length is 2 Of LIS The minimum value of the last element of ,k3 It means that the current sequence length is 3 Of LIS The minimum value of the last element of

that dp[i][k1][k2][k3] The number of schemes representing the corresponding situation .

Then enumerate one more at a time x, Yes x The size of can be classified and discussed .

See details 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;
 }