Solved:2
rank:306
跑路场.....
A.PACM team
简单背包记录路径都写挂 退役算了
#include <bits/stdc++.h> using namespace std; int p[40]; int a[40]; int c[40]; int m[40]; int g[40]; int dp[37][37][37][37]; int vis[40]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d%d%d%d%d", &p[i], &a[i], &c[i], &m[i], &g[i]); int P, A, C, M; scanf("%d%d%d%d", &P, &A, &C, &M); for(int i = 1; i <= n; i++) { for(int i1 = P; i1 >= p[i]; i1--) for(int i2 = A; i2 >= a[i]; i2--) for(int i3 = C; i3 >= c[i]; i3--) for(int i4 = M; i4 >= m[i]; i4--) dp[i1][i2][i3][i4] = max(dp[i1][i2][i3][i4], dp[i1 - p[i]][i2 - a[i]][i3 - c[i]][i4 - m[i]] + g[i]); } int cnt = 0; int tmp = P, tma = A, tmc = C, tmm = M; for(int i = n; i >= 1; i--) { if(tmp < p[i] || tma < a[i] || tmc < c[i] || tmm < m[i]) continue; if(dp[tmp][tma][tmc][tmm] == dp[tmp - p[i]][tma - a[i]][tmc - c[i]][tmm - m[i]] + g[i]) { vis[i] = 1; cnt++; tmp -= p[i]; tma -= a[i]; tmc -= c[i]; tmm -= m[i]; } } printf("%d ", cnt); for(int i = 1; i <= n; i++) { if(vis[i]) { cnt--; if(cnt) printf("%d ", i - 1); else printf("%d ", i - 1); } } return 0; }
E.Sort String
next数组的应用
#include <bits/stdc++.h> using namespace std; char s[1000005]; int nex[1000005]; void getfail(char *s, int* f) { f[0] = f[1] = 0; int len = strlen(s); for(int i = 1; i < len; i++) { int j = f[i]; while(j && s[i] != s[j]) j = f[j]; f[i + 1] = s[i] == s[j] ? j + 1 : 0; } } int main() { scanf("%s", s); getfail(s, nex); int len = strlen(s); if(len % (len - nex[len]) == 0 && len / (len - nex[len]) != 1) { int cir = len - nex[len]; int cn = len / cir; printf("%d ", cir); for(int j = 0; j < cir; j++) { printf("%d", cn); for(int k = j; k < len; k += cir) printf(" %d", k); puts(""); } } else { printf("%d ", len); for(int i = 0; i < len; i++) printf("%d %d ", 1, i); } return 0; }