首页 > 其他分享 >SP15637 GNYR04H - Mr Youngs Picture Permutations 解析

SP15637 GNYR04H - Mr Youngs Picture Permutations 解析

时间:2024-11-07 22:08:14浏览次数:1  
标签:Picture int Permutations Youngs len vector include

SP15637 GNYR04H - Mr Youngs Picture Permutations 解析

题目链接

分析题目性质

大意就是给 \(k\) 排然后每个数列单调,每个横列单调,求满足这样排列的方案数。

我们发现:与其为每个位置分配某个学生不如考虑将每个学生分给某个位置

思路

根据以上,不妨设:\(f_{a_1,a_2,a_3,a_4,a_5}\) 分别代表第 \(i\) 排现在人数为 \(a_i\) 的方案数。

那么应该满足以下条件:

  • \(a_i < N_i\)
  • \(i=1\) 或者 \(a_{i-1}<a_i\)

转移是简单的。

需要注意的是数组。

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
int k,len[35];
signed main(){
	for (;~scanf("%lld",&k);) {
		if (k == 0) break;
		for (int i = 0;i <= 5;i ++) len[i] = 0;
		for (int i = 1;i <= k;i ++) scanf("%lld",&len[i]);
		vector<vector<vector<vector<vector<int>>>>> f(
		    len[1] + 1, 
			vector<vector<vector<vector<int>>>>(
		        len[2] + 1, 
		        vector<vector<vector<int>>>(
		            len[3] + 1, 
		            vector<vector<int>>(
		                len[4] + 1, 
		                vector<int>(
		                    len[5] + 1,
		                    0
		                )
		            )
		        )
		    )
		);
	    f[0][0][0][0][0] = 1;
	    for (int a1 = 0;a1 <= len[1];a1 ++)
	    	for (int a2 = 0;a2 <= len[2];a2 ++)
	    		for (int a3 = 0;a3 <= len[3];a3 ++)
	    			for (int a4 = 0;a4 <= len[4];a4 ++)
	    				for (int a5 = 0;a5 <= len[5];a5 ++) {
	    					if (a1 < len[1]) f[a1 + 1][a2][a3][a4][a5] += f[a1][a2][a3][a4][a5];
	    					if (a2 < len[2] && a2 < a1) f[a1][a2 + 1][a3][a4][a5] += f[a1][a2][a3][a4][a5];
							if (a3 < len[3] && a3 < a2) f[a1][a2][a3 + 1][a4][a5] += f[a1][a2][a3][a4][a5];
							if (a4 < len[4] && a4 < a3) f[a1][a2][a3][a4 + 1][a5] += f[a1][a2][a3][a4][a5];
							if (a5 < len[5] && a5 < a4) f[a1][a2][a3][a4][a5 + 1] += f[a1][a2][a3][a4][a5];
						}
		printf("%lld\n",f[len[1]][len[2]][len[3]][len[4]][len[5]]);
	}
	return 0;
}

标签:Picture,int,Permutations,Youngs,len,vector,include
From: https://www.cnblogs.com/high-sky/p/18534113

相关文章

  • PictureBox实现进入换色,离开换色,点击换色
    实现和Word标题栏类似的效果可以看到有三种颜色:默认时是(243,243,243),鼠标进入时是这样(210,210,210),鼠标按下的瞬间变为了(177,177,177)4个关键事件:MouseEnter、MouseLeave、MouseDown、MouseUpMouseEnter:在鼠标进入控件的可见部分时发生privatevoidpictu......
  • SS240930B. 字符画(picture)
    SS240930B.字符画(picture)在一个\(10^7\times10^7\)的格子里,涂上至多\(900\)个格子。满足不存在一个格子恰好\(1\)个或\(3\)个相邻位置被涂色,定义恰好四个相邻格子都涂了颜色的格子是好的格子。构造一种涂色方案使得好的格子数量恰好是\(n\le300\)。涂颜色的格子和......
  • 题解 ARC118E【Avoid Permutations】/ SS240928D【d】
    题目描述对于一个排列\(a\),定义其权值如下:生成一个\((n+2)\times(n+2)\)的网格图,行列标号为\(0∼n+1\),每次可以从\((i,j)\)走到\((i,j+1)\)或\((i+1,j)\),且不能走到\((i,a_i)\),权值为从\((0,0)\)走到\((n+1,n+1)\)的方案数。现在排列\(......
  • WPF canvas Draw line , ellipse and rectangle, save canvas and contents as pictu
    //xaml<Windowx:Class="WpfApp417.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.mi......
  • WPF Image show picture in high resolution periodically via System.Timers.Timer
    <Windowx:Class="WpfApp411.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.microsoft......
  • Python可视化过程中.pictures.add这里一直报错,不明原因
    大家好,我是Python进阶者。一、前言前几天在Python白银交流群【沐子山树】问了一个Python可视化的问题,问题如下:importmatplotlib.pyplotasplt#创建一个简单的图表fig,ax=plt.subplots()ax.plot([1,2,3,4])ax.set_ylabel('somenumbers')#保存图表为PNG文件temp......
  • Python可视化过程中.pictures.add这里一直报错,不明原因
    大家好,我是Python进阶者。一、前言前几天在Python白银交流群【沐子山树】问了一个Python可视化的问题,问题如下:importmatplotlib.pyplotasplt#创建一个简单的图表fig,ax=plt.subplots()ax.plot([1,2,3,4])ax.set_ylabel('somenumbers')#保存图表为PNG文件temp......
  • WPF Combobox switch up and down then show the big picture in the right part
    <ComboBoxx:Name="cbx"Grid.Row="0"Grid.Column="0"SelectedIndex="0"ItemsSource="{StaticResourcebooksData}"FontSize="20"......
  • Baby Ehab Plays with Permutations 题解
    前言题目链接:Codeforces;洛谷。题意简述你有一个长度为\(n\)的序列\(p\)满足\(p_i=i\),你可以进行\(x\)次操作,每次操作找到两个不同的\(i,j\)并且交换\(p_i,p_j\),问最终有几个可能的序列。分别求出\(x=1,\ldots,k\)时的答案。\(1\len\le10^9\),\(1\lek\le......
  • WPF C# split picture into small pieces and show in grid cells
    usingSystem;usingSystem.Collections.Generic;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;usingSystem.Windows;usingSystem.Windows.Controls;usingSystem.Windows.Data;usingSystem.Windows.Documents;using......