围栏木桩 码蹄集-爱代码爱编程

题目来源：码蹄集

题目描述：

大致思路：

1. 对于每个问题，首先读取木桩的高度序列。
2. 创建两个数组b和c，其中b[i]表示以第i根木桩结尾的最长升序序列的长度，c[i]表示以第i根木桩结尾的最长升序序列的方案总数。
3. 通过遍历木桩序列，使用动态规划的思想，计算b和c数组的值。
4. 遍历b数组，找到最大的长度max_length，以及对应的木桩编号max_index。
5. 使用max_length和max_index计算方案总数C，即遍历b数组，找到所有长度等于max_length且木桩编号小于等于max_index的木桩，将对应的方案总数c[i]累加起来。
6. 输出最大木桩数量t和方案总数C。

Python代码实现：

def solve():
    m = int(input())
    for _ in range(m):
        n, *heights = map(int, input().split())
        b = [1] * (n + 1)
        c = [1] * (n + 1)

        for j in range(2, n + 1):
            for r in range(j - 1, 0, -1):
                if heights[j - 1] >= heights[r - 1]:
                    if b[j] < b[r] + 1:
                        b[j] = b[r] + 1
                        c[j] = c[r]
                    elif b[j] == b[r] + 1:
                        c[j] += c[r]

        max_length = max(b)
        max_index = b.index(max_length)
        max_count = 0

        for i in range(1, n + 1):
            if b[i] == max_length and heights[i - 1] <= heights[max_index - 1]:
                max_count += c[i]

        print(max_length, max_count)


solve()

Java代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        while (k > 0) {
            k--;
            int n = scanner.nextInt();
            int[] a = new int[2005];
            int[] b = new int[2005];
            int[] c = new int[2005];
            for (int i = 1; i <= n; i++) {
                a[i] = scanner.nextInt();
                b[i] = c[i] = 1;
            }
            for (int j = 2; j <= n; j++) {
                int r;
                for (r = j - 1; r >= 1; r--) {
                    if (a[j] >= a[r]) {
                        if (b[j] < b[r] + 1) {
                            b[j] = b[r] + 1;
                            c[j] = c[r];
                        } else if (b[j] == b[r] + 1) {
                            c[j] += 1;
                        }
                    }
                }
            }
            int max = -1;
            int bj = 0;
            for (int i = 1; i <= n; i++) {
                if (b[i] > max) {
                    max = b[i];
                    bj = i;
                }
            }
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                if (b[i] == b[bj]) {
                    ans += c[i];
                }
            }
            System.out.println(b[bj] + " " + ans);
        }
    }
}

C++代码实现：

参考链接：https://yxsmarter.blog.csdn.net/article/details/128209412?spm=1001.2014.3001.5502

#include<bits/stdc++.h>
using namespace std;

int main(){
    int k,n,b[2005],c[2005],a[2005],i,j;
    cin>>k;
    while(k--){
        cin>>n;
        for(i=1;i<=n;i++){
            cin>>a[i];
            b[i]=c[i]=1;
        }
        for(j=2;j<=n;j++){
            int r;
            for(r=j-1;r>=1;r--){
                if(a[j]>=a[r]){
                    if(b[j]<b[r]+1){
                        b[j]=b[r]+1;
                        c[j]=c[r];
                    }else if(b[j]==b[r]+1){
                    c[j]+=1;
                    }   
                }
            }
        }
        int max=-1,bj=0;
        for(i=1;i<=n;i++){
            if(b[i]>max){
                max=b[i];
                bj=i;
            }
        }   
        int ans=0;
        for(i=1;i<=n;i++){
            if(b[i]==b[bj]) ans+=c[i];
        }
        cout<<b[bj]<<" "<<ans<<endl;
    }
    
    return 0;
}

代码提交测试结果：

附B站老师思路讲解链接，可供参考：https://www.bilibili.com/video/BV1ih4y1x7su/?t=1338.5