首页 > 试题广场 >

不等式数列

[编程题]不等式数列

热度指数：4030 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 '>' 和 '<' )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即('<'')和n-k-1个大于符号(即'>'),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

输入描述:

输入包括一行,包含两个整数n和k(k < n ≤ 1000)

输出描述:

输出满足条件的排列数,答案对2017取模。

示例1

输入

5 2

输出

算法知识视频讲解

wangwenbin

// 按照赞最多的实现的dp

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
        	int n = sc.nextInt();
        	int k = sc.nextInt();
            int[][] dp = new int[n+1][k+1];
            for(int i=0;i<=n;i++)dp[i][0] = 1;
            for(int i=2;i<n+1;i++){
                for(int j=1;j<=k && j<i;j++){
                    if(j==i-1)dp[i][j]=1;
                    else if(i>j-1){
                        dp[i][j] = (dp[i-1][j-1]*(i-j) + dp[i-1][j]*(j+1))%2017;
                    }
                }
            }
            System.out.println(dp[n][k]);
        }
        
    }
}

编辑于 2017-08-24 09:22:40 回复(5)

liliechao1

//根据最高赞答案，写的java代码，感谢！
import java.util.Scanner;

public class Main{
    static int dp[][];
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		dp = new int[n][k+1];
		
		for(int i = 1;i<n;i++){
			dp[i][0] = 1;
		}
		
		System.out.print(permutationAmount(n,k));
	}
	
	public static int permutationAmount(int n ,int k){
		if(n == 2 && k == 0){
			dp[n-1][k] = 1;
			return dp[n-1][k];
		}
		if(n == 2 && k == 1){
			dp[n-1][k] = 1;
			return dp[n-1][k];
		}
		
		if(n<=k)
			return 0;
		if(dp[n-1][k] != 0)
			return dp[n-1][k];
		
		dp[n-1][k] = (permutationAmount(n-1,k-1)*(n-k)+permutationAmount(n-1,k)*(k+1))%2017;
		
		return dp[n-1][k];
	}
}

发表于 2017-06-13 22:51:44 回复(0)

北风乱九州

我用的是python，思路按照上面的大神提供的动态规划的思路，不过时间超时太多，最后只通过60%。

我是按照杨辉三角形的形式构造了一个从上到下的三角形，最上面是（2-0）（2-1）（2-2）

第二行是（3-0）（3-1）（3-2）（3-3），按照这么一个排列，最左边一列都是（n-0），结果都是1，最右边一列都是（n-n），结果都是0.由此构造了一个不断增加的动态列表，代码如下：

import time

a1 = raw_input()

print 'start:',time.ctime()

a2 = a1.split(' ')

b1 = []

for x in a2:

b1.append(int(x))

i = b1[0]

j = b1[1]

ix = int(0.5*(i+3)*(i-2) + j)

l = [1 ,1 ,0 ,1]

if len(l) < ix + 2:

for x in range(4,ix+1):

for t in range(3,i+1):

if (0.5*(t+3)*(t-2)-1) < x < 0.5*(t+3)*(t-2)+t+1:

a = t

b = int(x - 0.5*(a+3)*(a-2))

if b==0:

u=1

l.append(u)

break

elif a==b:

u=0

l.append(u)

else:

u = int((l[int(0.5*(a+2)*(a-3)+b-1)])*(a-b)+(l[int(0.5*(a+2)*(a-3)+b)])*(b+1))%2017

l.append(u)

break

else:

pass

c = l[ix]

print c

print 'stop:',time.ctime()

因为结果提示超时，我就增加了time模块，想看看到底速度差了多少。

从上面的图片看差的蛮多的，还需要继续改进。

发表于 2017-06-05 09:36:56 回复(0)

Python

xNazgul

dp的python实现，AC

def permute(n, k):
    cur_d = {i: 1 for i in range(n - k)}
    pre_d = {}
    for j in range(1, k + 1):
        pre_d = cur_d
        cur_d = {0: 1}
        for i in range(1, n - k):
            cur_d[i] = pre_d[i] * (i + 1) + cur_d[i - 1] * (j + 1)
    return cur_d[n - k - 1]

编辑于 2018-04-17 02:11:03 回复(1)

牛客第一菜


	 



	//很直观的dp，dp[i][j]是前i个数小于符号为j个时的排列个数



	importjava.util.*;



	publicclassMain {



	    publicstaticvoidmain(String[] args){



	        Scanner in=newScanner(System.in);



	        intn=in.nextInt();



	        intk=in.nextInt();



	        int[][] dp=newint[n][k+1];



	        intmod=2017;



	        dp[1][0]=1;



	        dp[1][1]=1;



	        for(inti=2;i<n;++i){



	            for(intj=0;j<=Math.min(k, i);++j){



	                if(j==0){



	                    dp[i][j]=dp[i-1][0];



	                    continue;



	                }



	                dp[i][j]=(dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j+1))%mod;



	            }



	        }



	        System.out.println(dp[n-1][k]);



	        in.close();



	    }



	}

发表于 2017-09-01 23:42:36 回复(0)

_chaos_


	#include <iostream>



	using namespace std;



	intmain() {



	    intn, k;



	    cin >> n >> k;



	    int**dp = newint*[n + 1]();



	    for(inti = 0; i < n + 1; ++i)



	        dp[i] = newint[i]();



	    for(inti = 1; i < n + 1; ++i)



	        dp[i][0] = dp[i][i - 1] = 1;



	    for(inti = 3; i < n + 1; ++i)



	        for(intj = 1; j < i - 1; ++j)



	            dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) % 2017;



	    cout << dp[n][k] << endl;



	    for(inti = 0; i < n + 1; ++i)



	        delete[] dp[i];



	    delete[] dp;



	    return0;



	}

编辑于 2017-06-17 17:16:36 回复(0)

→①年前↑

为啥还是90%呢？

代码：

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int k = scanner.nextInt();

int[][] dp = new int[1000][1000];

for (int i = 1; i <=n; i++) {

dp[i][0]=1;

}

for (int i = 2; i <=n; i++) {

for (int j = 1; j <= k; j++) {

dp[i][j]=(dp[i-1][j-1]*Math.abs(i-j)+dp[i-1][j]*(j+1))%2017;

}

System.out.println(dp[n][k]%2017);

scanner.close();

}

发表于 2017-04-29 17:29:49 回复(3)

RomanMJ

dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) % 2017;

dp[i][j]表示有i个数字及j个小于号所能组成的数量(大于号数量当然是i - j - 1次，后面需要使用)

而加入第i + 1个数字时，分以下四种情况：

1.如果将i+1插入当前序列的开头，即有了1<2，加入后成为3>1<2，会发现等于同时加入了一个大于号！(此时可以无视1与2之间的关系，因为i+1>i)

2.如果将i+1插入当前序列末尾,即1<2变成了 1<2<3，会发现等于同时加入了一个小于号！ (此时可以无视1与2之间的关系，因为i+1>i)

3.如果将i+1加入一个小于号之间，即已经有 1<2了，向中间加入3,会发现变成了1<3>2，等于同时加入了一个大于号！

4.如果将i+1加入一个大于号中间，即有了2>1，变成了2<3>1，等于同时加入了一个小于号！

综上所述，dp[i][j]等于以上四种情况之和：

dp[i - 1][j] 将i加在开头等于加入一个大于号，即要求i-1个数时已经有了j个小于号

dp[i - 1][j - 1] 将i加在末尾等于加入一个小于号，即要求i-1个数时已经有了j-1个小于号

dp[i - 1][j] * j 将i加在任意一个小于号之间，等于加入了一个大于号；即要求i-1个数时已经有了j个小于号，每个小于号都可以进行这样的一次插入

dp[i - 1][j - 1] * (i- j - 1) 将i加载任意一个大于号之间，等于加入了一个小于号；即要求i-1个数时有了j-1个小于号，而此时共有

(i - 1) - (j - 1)- 1个大于号，每个大于号都要进行一次这样的操作合并同类项即为

dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1))

最后要记得取模

编辑于 2017-09-03 17:05:20 回复(23)

z按时

#include <iostream>

#include <string.h>

using namespace std;

int dp[1001][1001];

int main()

{

int n,k,d;

while(~scanf("%d%d",&n,&k))

{

d=0;

memset(dp,0,sizeof(dp));

dp[1][0]=1;

for(int i=2; i<=n; i++)

for(int j=0; j<n; j++)

{

if(j==0)

dp[i][j]=1;

else

{

dp[i][j]=(dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1))%2017;

}

printf("%d\n",dp[n][k]);

}

return 0;

}

运用动态规划思想

发表于 2017-04-28 14:04:06 回复(4)

为啥要起名字

import sys
n,k=list(map(int,sys.stdin.readline().strip().split()))
dp=[[0]*(k+1) for i in range(n+1)]
for i in range(1,n-k+1):
dp[i][0]=1 ##边界条件，当没有小于号时，只有大于号可能是只有一种排序方法
for i in range(2,n+1):
for j in range(1,k+1):
dp[i][j]=(dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1))%2017
print(dp[n][k])

发表于 2018-05-15 15:03:48 回复(0)

夜华

#include <iostream>

#include <algorithm>

using namespace std;

int main(){

int n,k;

cin>>n>>k;

int dp[n+1][n];

for(int i=1;i<=n;i++){

dp[i][0]=dp[i][i-1]=1;

}

for(int i=3;i<=n;i++){

for(int j=1;j<i-1;j++){

dp[i][j]=(dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1))%2017;

}

cout<<dp[n][k]<<endl;

return 0;

}

发表于 2017-07-10 18:17:07 回复(0)

Bostonpigeons

遇事不决先打表
1 
1 1
1 4 1 
1 11 11 1 
1 26 66 26 1
1 57 302 302 57 1
1 120 1191 2416 1191 120 1
然后找规律->AC
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<bits/stdc++.h>
using namespace std;
int z[1005];
int a[1005];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        z[i]=i;
    }
    do{
        int sum=0;
        for(int i=0;i<n;i++){
            if(z[i]<z[i+1]) sum++;
        }
        a[sum]++;
    }while(next_permutation(z,z+n));
    for(int i=0;i<n;i++) {
        cout<<i<<' '<<a[i]<<endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<bits/stdc++.h>
using namespace std;
int z[1005][1005];
int a[1005];
int main()
{
   //  freopen("in","r",stdin);
    for(int i=0;i<1005;i++) z[i][i-1]=z[i][0]=1;
    for(int i=2;i<1005;i++){
        for(int j=1;j<i;j++){
            z[i][j]=(j+1)*z[i-1][j]+(i-j)*z[i-1][j-1];
            z[i][j]%=2017;
        }
    }
    int n,k;
    cin>>n>>k;
    cout<<z[n][k]<<endl;
    return 0;
}

发表于 2019-06-27 22:03:15 回复(1)

Jerry1127

package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	dp := make([][]int, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, k+1)
	}

	for i := 0; i <= n; i++ {
		dp[i][0] = 1
	}
	for i := 2; i < n+1; i++ {
		for j := 1; j <= k && j < i; j++ {
			if j == i-1 {
				dp[i][j] = 1
			} else if i > j-1 {
				dp[i][j] = (dp[i-1][j-1]*(i-j) + dp[i-1][j]*(j+1))%2017
			}
		}
	}
	fmt.Println(dp[n][k])
}

发表于 2022-03-29 16:33:55 回复(0)

牛客511771125号

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<iomanip>
using namespace std;


int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> dp(n, 0);
	dp[0] = dp[1] = 1;
	//cout<<setw(3)<< 1 << ' ' << setw(3) << 1 << ' '<< setw(3) << 0 << ' ' << setw(3) << 0 << ' ' << setw(3) << 0 << endl;
	for (int i = 3; i <= n; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (j != 0) dp[j] = ((i - j) * dp[j - 1] + (j + 1) * dp[j])%2017;
			else dp[j] = ((j + 1) * dp[j])%2017;
		}
		//for (int j = 0; j < n; j++) cout << setw(3)<< dp[j] << ' ';
		//cout << endl;
	}
	cout << dp[k];
}

发表于 2021-04-02 11:38:21 回复(0)

我是一只小熊

用c语言来实现
#include <stdio.h>
#include <stdlib.h>
int  d[1005][1005];
int main()
{
    int n,k;
    int i,j;
    while(scanf("%d %d",&n,&k)!=EOF)
    {
        for(i=1;i<=n;i++)
            for(j=0;j<=k;j++)
                d[i][j]=0;
        for(i=1;i<=n;i++)
        {
            d[i][0]=1;
        }
        for(i=2;i<=n;i++)
        {
            for(j=1;j<=k;j++)
            {
                d[i][j]=d[i-1][j-1]+d[i-1][j]+d[i-1][j]*j+d[i-1][j-1]*(i-j-1);
                d[i][j]=d[i][j]%2017;
            }
        }
        printf("%d\n",d[n][k]);
    }
    return 0;
}

发表于 2018-09-04 15:10:40 回复(0)

深度学习ing的人

#include<iostream>
#include<string.h>
using namespace std;

int main()
{
    int n, k;
    cin>>n>>k;
    int dp[n+1][n];
    memset(dp,0,sizeof(dp));
    dp[1][0]=1;
    for(int i=2; i<=n; ++i)
        for(int j=0; j<n; ++j)
        {
            if(j==0)
                dp[i][j]=1;
            else
                dp[i][j]=(dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j))%2017;
        }
    cout<<dp[n][k]<<endl;
    return 0;
}

发表于 2018-06-11 16:01:55 回复(0)

逗比请来的猴子

import java.util.Scanner;

/*
 *
 * 参考大神的解题思路：https://www.nowcoder.com/test/question/done?tid=14939450&qid=95828#summary
 * 使用动态规划，真的难想，话说只有动态规划才适合此题
 *
 * dp[i][j] 表示i个序列有j个'<',对于i+1个序列，可以进行如下分析
 * 1.直接添加到最开始，此时多添加一个>,种类数+dp[i-1][j];
 * 2.直接添加到最后面，此时多添加一个<,种类数+dp[i-1][j-1];
 * 3.添加到中间任意一个<,例如1<2，变成1<3>2,多添加了一个>，种类数+dp[i-1][j]*j;
 * 4.添加到中间任意一个>，例如2>1,变成2<3>1,多添加了一个<,种类数+dp[i-1][j-1]*(i-j-1)
 * 整理可得到：dp[i][j] = dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j)
 *
 * */
public class Inequtation {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int[][] dp = new int[n + 1][k + 1];
            for (int i = 1; i <= n; i++) {
                dp[i][0] = 1;
            }
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= k; j++) {
                    dp[i][j] = (dp[i - 1][j] * (j + 1) + dp[i - 1][j - 1] * (i - j)) % 2017;
                }
            }
            System.out.println(dp[n][k]);
        }
    }
}

编辑于 2018-04-09 09:05:35 回复(2)

凝视深空

简单DP问题。唯一要注意一点的就是所有数据都要%2017，

否则对于大一点的数据就直接溢出

#include <stdio.h>

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    long long dp[1001][1001] = {0};
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= (i % 2 == 0 ? i >> 1 - 1 : i >> 1); ++j) {
            if (j == 0) {
                dp[i][j] = 1;
            }
            else if (j == 1) {
                dp[i][j] = (dp[i - 1][j] * 2 + i - 1) % 2017;
            }
            else {
                dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) % 2017;
            }
            dp[i][i - j - 1] = dp[i][j];
        }
    }
    printf("%lld\n", dp[n][k] % 2017);
    return 0;
}

发表于 2018-02-23 15:46:56 回复(0)

lqqqdu

package BaiduCorrect;

import java.util.Scanner;

public class test5 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        
        int [] [] dp = new int[1001][1001];
        dp[1][0] = 1;
        for(int i = 2;i <= n;i++){
            for(int j = 0;j < n;j++){
                if(j == 0){
                    dp[i][j] = 1;
                }
                else {
                    dp[i][j]=(dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1))%2017;
                }
            }
        }
        System.out.println(dp[n][k] % 2017);
    }

}

发表于 2017-11-27 21:24:05 回复(0)

JavaScript

楼西

var ins = readline().split(" ");
var n = parseInt(ins[0]);
var num = parseInt(ins[1]);
function numbers(total, k){
    var arr = [];
    for(var i=0; i<total+1; i++){
        arr[i] = [];
        arr[i][0] = 1;
    }
    for(var j=0; j<k+1; j++){
        arr[0][j] = 0;
    }
    for(var n=1; n<total+1; n++){
        for(var m=1; m<k+1; m++){
            arr[n][m] = (arr[n-1][m-1]*(n-m) + arr[n-1][m]*(m+1))%2017;
        }
    }
    return arr[total][k];
}
print(numbers(n, num));

发表于 2017-11-22 15:28:34 回复(0)