太水了,40分钟水了前3题就做不动了。第四题看出来是DP,但不会做,真是弱爆了。
A。大水,不说了。
B。统计【a,b】的数量,就是求F【a】- F【b】,F【i】表示[1,i]的数量,预处理F数组即可
C。排序,每次累加最大的1个,4个,16个,。。。4^n个数。
D.确实自己太水,不看题解想不出来。
注意到m非常大,其实首先维护直接fix一段区间的最小花费a[i][j],然后
DP[i][j]表示前i个洞,修j个的最小花费,
DP[i][j]=min(dp[i][j], dp[k][j - i + k] + a[k + 1][i])
/* * D.cpp * * Created on: 2013-5-30 * Author: zy */ #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #include<set> #include<map> #include<vector> #include<string> using namespace std; const int maxn = 305; const long long inf = 0xffffffffffffLL; int n, m, t; long long dp[maxn][maxn], a[maxn][maxn]; int main() { for (int i = 0; i < maxn; i++) for (int j = 0; j < maxn; j++) a[i][j] = dp[i][j] = inf; scanf("%d%d%d", &n, &m, &t); for (int i = 1; i <= m; i++) { int x, y, c; scanf("%d%d%d", &x, &y, &c); a[x][y] = c < a[x][y] ? c : a[x][y]; } for (int i = 1; i <= n; i++) for (int j = n; j >= i; j--) { a[i][j] = min(a[i][j + 1], a[i][j]); a[i][j] = min(a[i - 1][j], a[i][j]); } long long ans = inf; dp[0][0] = 0; for (int i = 1; i <= n; i++) { dp[i][0] = 0; for (int j = 1; j <= i; j++) { dp[i][j] = dp[i - 1][j]; for (int k = i - j; k <= i - 1; k++) dp[i][j] = min(dp[i][j], dp[k][j - i + k] + a[k + 1][i]); if (j >= t) ans = min(ans, dp[i][j]); } } if (ans == inf) ans = -1; cout << ans << endl; return 0; }
E。。。。