草庐IT

CF888D Almost Identity Permutations 题解

201929未来の回忆录 2023-03-28 原文

CF链接：Almost Identity Permutations

Luogu链接：Almost Identity Permutations

$ {\scr \color {Cyan}{\text{Solution}}} $

前言

这好像是一道能用数学秒掉的题目

但由于我喜欢DP过菜，我们用DP来解决这个问题

分析

$ dp[i][j] $ 表示在 $ i $ 个数里有 $ j $ 个数位置满足 $ a[i]==i $

答案很简单，就是$\sum_{i=n-k}^{n} dp[n][i]$

接下来考虑状态如何转移

$ dp[i][j] $ 可以由 $ dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1] $ 转移而来

  • 从 $ dp[i−1][j−1] $ 转移，我们可以直接把新增的数放到增加的位置上去就可以了；
  • 从 $ dp[i−1][j] $ 转移，新增的数不能放到自己的位置上，且必须要和$ i-1-j $个其他的数字交换位置；
  • 从 $ dp[i-1][j+1] $转移，那么新增的数字和原先在自己位置上的数字（j+1种）可以进行交换（因为现在多了一个，所以要减少一个）；

边界也要稍稍注意一下

$ j=0 $时，并没有$ dp[i-1][j-1]$

同理，$ i=j $时，直接为$ 1 $

诶，做完了

Code:

//From:201929
#include<bits/stdc++.h>
#define L long long
using namespace std;
L dp[1005][1005];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    dp[4][4]=1,dp[4][3]=0,dp[4][2]=6,dp[4][1]=8,dp[4][0]=9;
    for(int i=5;i<=n;i++)
    for(int j=0;j<=i;j++)
    if(j==0) dp[i][j]=(i-1)*dp[i-1][j]+dp[i-1][1];
    else if(j==i) dp[i][j]=1;
    else dp[i][j]=dp[i-1][j-1]+(i-1-j)*dp[i-1][j]+(j+1)*dp[i-1][j+1];
    L ans=0;
    for(int i=n-k;i<=n;i++) ans+=dp[n][i];
    printf("%lld",ans);
    return 0;
}

 

题解PermutationsspancolorstyleC++

有关CF888D Almost Identity Permutations 题解的更多相关文章

  1. 【算法题解】20. 两数之和 - 2

    这是一道简单题题目来自：https://leetcode.cn/problems/two-sum/题目给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。提示：22nums.length104−109−109nums[i]109−109−109target109只会存在一个有效答案进阶：你可以想出一个时间复杂度小于O(n2)O(n^2)O(n2)的算法吗？示例1：输入：nums=[2,7,11,15],targe

  2. javascript - 使用 javascript 获取 Cloudflare 的 HTTP_CF_IPCOUNTRY header ？ - 2

    有很多关于如何使用javascript获取httpheader的问题，但由于某些原因，它们没有显示HTTP_CF_IPCOUNTRYheader。如果我尝试使用phpecho$_SERVER["HTTP_CF_IPCOUNTRY"];，它会工作，所以CF工作得很好。是否可以使用javascript获取此header？ 最佳答案 @Quentin的回答是正确的，适用于任何试图访问服务器header的javascript客户端。但是，由于这个问题特定于Cloudlfare，并且特定于在HTTP_CF_IPCOUNTRYheader中正常

  3. 蓝桥杯第十四届省赛完整题解 C/C++ B组 - 2

    没有测评，不知道对不对，仅仅过样例而已试题A:日期统计本题总分：5分【问题描述】小蓝现在有一个长度为100的数组，数组中的每个元素的值都在0到9的范围之内。数组中的元素从左至右如下所示：5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533现在他想要从这个数组中寻找一些满足以下条件的子序列：   1.子序列的长度为8；   2.这个子序列可以按照下标顺序组成一个yyyymmdd格式的日期，并且要求这个日期是2023年中的某一天的日期，例如202309

  4. javascript - CF连接到云 Controller - 2

    我使用以下库连接到云Controllerhttps://github.com/prosociallearnEU/cf-nodejs-clientconstendpoint="https://api.mycompany.com/";constusername="myuser";constpassword="mypass";constCloudController=new(require("cf-client")).CloudController(endpoint);constUsersUAA=new(require("cf-client")).UsersUAA;constApps=new

  5. 2023第十四届蓝桥杯C/C++B组省赛题解 - 2

    2023蓝桥C/C++B组省赛文章目录2023蓝桥C/C++B组省赛试题A:日期统计题目描述枚举参考代码试题B:01串的熵题目描述枚举|模拟参考代码试题C:冶炼金属题意描述取交集参考代码试题D:飞机降落题意描述DFS+剪枝，懒得写试题E:接龙数列题意描述DP参考代码试题F:岛屿个数题意描述dfs|连通块参考代码试题G:子串简写题意描述前缀和参考代码试题H:整数删除题意描述双向链表|最小堆参考代码试题I:景区导游题意描述带权LCA参考代码试题J:砍树题意描述树上差分参考代码试题A:日期统计题目描述【问题描述】小蓝现在有一个长度为100的数组，数组中的每个元素的值都在0到9的范围之内。数组中的元素

  6. linux - 构建 cf-cli : go build runtime: linux/386 must be bootstrapped using make. bash 时出错 - 2

    CloudFoundry的CLI工具位于cloudfoundry/cli是用围棋写的。我正在尝试构建CLI工具但出现此错误:gobuildruntime:linux/386必须使用make.bash引导如何解决这个问题？下面是cli/bin/build-all.sh脚本的内容:#!/bin/bashset-eset-xOUTDIR=$(dirname$0)/../outGOARCH=amd64GOOS=windows$(dirname$0)/build&&cp$OUTDIR/cf$OUTDIR/cf-windows-amd64.exeGOARCH=386GOOS=windows$(di

  7. LeetCode——链表简单题题解 - 2

    83.删除排序链表中的重复元素题目描述给定一个已排序的链表的头head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。输入：head=[1,1,2]输出：[1,2]解题思路：用一个指向节点类型的指针保存头结点，用另一个指向节点类型的指针对该链表进行遍历，由于是有序的，当出现不同的值就说明不会再出现跟前面的值相同的节点了，最后循环结束的条件是遍历到最后一个节点的时候，也就是该节点的next指向空的时候，停止循环，返回该保存的头结点，另外，如果传过来的头结点是空，则直接返回空。参考代码：/***Definitionforsingly-linkedlist.*structListNod

  8. NEUQ week 12 题解 - 2

    P1776宝物筛选宝物筛选题目描述终于，破解了千年的难题。小FF找到了王室的宝物室，里面堆满了无数价值连城的宝物。这下小FF可发财了，嘎嘎。但是这里的宝物实在是太多了，小FF的采集车似乎装不下那么多宝物。看来小FF只能含泪舍弃其中的一部分宝物了。小FF对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小FF有一个最大载重为WWW的采集车，洞穴里总共有nnn种宝物，每种宝物的价值为viv_ivi​，重量为wiw_iwi​，每种宝物有mim_imi​件。小FF希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。输入

  9. c# - XmlSerializer 在 .NET 3.5 和 CF.NET 3.5 之间有所不同 - 2

    我有一个在CF.NET和.NET下运行的库，但两者之间的序列化不同。因此，在CF.NET下生成的XML文件在.NET下不可读，这对我来说是个大问题!这里是代码示例:[Serializable,XmlRoot("config")]publicsealedclassRemoteHost:IEquatable{//...}publicclassProgram{publicstaticvoidMain(){RemoteHosthost=newRemoteHost("A");Listhosts=newList();hosts.Add(host);XmlSerializerser=newXmlSe

  10. 【Android Camera2】彻底弄清图像数据YUV420_888转NV21问题/良心教学/避坑必读! - 2

    前言  只要是使用AndroidCamera2开发相机相关功能的小伙伴，必然会和相机数据打交道吧。本文不讲解相机相关的操作，只是详细地讲解得到相机图像后，如何将图像Image转成NV21/NV12的数据的。  你可能会说，这个问题很普通了，网上都有现成的代码，拿过来直接用就行了~然而网上的代码大多数（最少我找到的）都是存在一定错误（或者是性能过低）。你是否存在如下问题？  是否遇到转成的NV21数据转成RGB可用，但是在使用OpenGL绘制图像时得不到正确纹理？转成的NV21数据在Java里可用，在Jni里却挂掉了？  是否遇到图像数据用的好好的，换一个图像分辨率代码就失效了？  这些都是我遇

随机推荐