题解 P3153 【[CQOI2009]跳舞】

这是一道动态规划题目。

首先，我们可以想到一个状态 $f_{i,j}$ 表示前 $i$ 个人跳舞，第 $i$ 个人跟第 $i-1$ 个人跳的舞种为 $j$ 的方案数。

然后，我们可以得到状态转移方程：

$$f_{i,j}=\sum_{k\neq j}f_{i-1,k}$$

即第 $i$ 个人可以跳除了 $j$ 以外的任何一种舞，因此我们枚举前面的人跳的舞种，转移即可。

最后，答案即为 $\sum_{i=1}^{n}\sum_{j=1}^{m}f_{i,j}$，表示前 $i$ 个人跳任何一种舞的方案数之和。

时间复杂度为 $O(nm^2)$，可以通过此题。

相关问题

P1161 开灯java题解

根据引用[2]提供的题解，以下是P1161 开灯的Java题解：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        boolean[] lights = new boolean[n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j % i == 0) {
                    lights[j] = !lights[j];
                }
            }
        }
        
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (lights[i]) {
                count++;
            }
        }
        
        System.out.println(count);
        scanner.close();
    }
}

这个题解使用了一个布尔数组`lights`来表示灯的状态，初始时所有灯都是关闭的。然后，通过两层循环遍历每个操作和每个灯，如果灯的编号能被操作的次数整除，就改变灯的状态。最后，统计打开的灯的数量并输出。

洛谷p2437C语言题解

以下是洛谷p2437 C语言题解的代码示例：

#include <stdio.h>

int main() {
    int n, i, j, s = 0;
    scanf("%d", &n);
    
    for (i = 1; i <= n; i++) {
        for (j = i; j <= n; j++) {
            s++;
            if (s < 10) {
                printf("0");
            }
            printf("%d", s);
        }
        printf("\n");
    }
    
    return 0;
}

该代码是一个嵌套循环，用于打印一个直角边长度为n的数字直角三角形。其中，外层循环控制行数，内层循环控制每行的数字个数。变量s用于记录当前要打印的数字，每次循环递增1。如果s小于10，则在打印之前加上前导0。最后，每行打印完后换行。