USACO 3.4.4 Raucous Rockers 解题报告

题目本质：动态规划？枚举？都像 算法描述：用f[i][j][k] 代表第i张碟子装了长度为j的歌, 而且最后一首是k。具体的方程看代码吧 复杂度：时间O(n^4), 空间O(n^3) / LANG: C ID: yylogoo1 PROG: rockers / #include #include #define MAX 21 int num[MAX]; int f[MAX][MAX][MAX]; int ans; int n, t, m; int main(int argc, char *argv[]) { int i, j, k, l; freopen("rockers.in", "r", stdin); freopen("rockers.out", "w", stdout); scanf("%d%d%d", &n, &t, &m); for(i = 1; i f[i][j + num[l]][l]){ f[i][j + num[l]][l] = f[i][j][k] + 1; } }else{ if(f[i][j][k] + 1 < f[i + 1][num[l]][l]){ f[i + 1][num[l]][l] = f[i][j][k] + 1; } } } if(ans