这个题目是贪心，开始我以为是背包，不过也不太好背包，因为这个L都已经是1e9了。
这个题目怎么贪心呢？它是因为这里有一个二倍的关系，所以说val[i]=val[i-1]*2
所以利用这个关系，我们可以求出每一个体积的最小的花费。
这个处理完之后，我们就可以开始处理题目中的L了。
这个L，从高位开始枚举，先求出L个中最多并且要小于等于这个最大值可以用的这个物品的数量，然后如果是小于，那么再多选一次，这样肯定会超出体积，
不过这样就保证了大于等于L。
对于下面一个L取完膜之后继续这样处理，最后求出最小值。
#include <cstdio> #include <cstring> #include <queue> #include <cstdlib> #include <algorithm> #include <vector> #include <iostream> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; const int maxn = 1e5 + 10; ll val[50]; int main() { int n; ll L; scanf("%d%I64d", &n, &L); for (int i = 1; i <= n; i++) scanf("%I64d", &val[i]); for (int i = 2; i <= n; i++) val[i] = min(val[i], val[i - 1] * 2); ll ans = inf64, sum = 0; for(int i=n;i>=1;i--) { ll len = 1 << (i - 1); ll num = L / len; sum += num * val[i]; L %= len; ans = min(ans, sum + (L > 0)*val[i]); } printf("%I64d ", ans); return 0; }
这个题目其实比较简单，就是找规律，如果找出来了，就很简单了。
首先我发现如果每一行有两个不同的数，那么肯定是可以的，然后lj发现如果最后一行有两个不相同的数，那么肯定也是可以的，最后就可以推出来
如果任意一行有两个数不同，那么肯定也是可以的。
这样子就很简单了。
#include <cstdio> #include <cstring> #include <queue> #include <cstdlib> #include <algorithm> #include <vector> #include <iostream> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; const int maxn = 1e5 + 10; int mp[550][550]; int main() { int n, m; scanf("%d%d", &n, &m); int flag = 0, mark = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &mp[i][j]); if (!flag&&j > 1 && mp[i][j] != mp[i][1]) { flag = i; mark = j; } } } if (!flag) { int ans = 0; for (int i = 1; i <= n; i++) ans ^= mp[i][1]; if (ans == 0) printf("NIE "); else { printf("TAK "); for (int i = 1; i < n; i++) printf("1 "); printf("1 "); } } else { printf("TAK "); int ans = 0; for (int i = 1; i <= n; i++) ans ^= mp[i][1]; if(ans) { for (int i = 1; i < n; i++) printf("1 "); printf("1 "); } else { for(int i=1;i<=n;i++) { if (i == flag) printf("%d ", mark); else printf("1 "); } printf(" "); } } return 0; }
这个题目其实很不好想，这个是lj一步步引导我才写出来的，
首先这个题目每一个位置可以往后面推出 1~k 所以算一下复杂度是1e7
dp[i]表示以 i 为最后一个值，从 1~i 的最大的分完组之后的和。
所以这个就有刷表法和填表法，
就是从这个状态往后推和每一个状态从前面推过来，第一个很好写，后面那个比较难。
#include <cstdio> #include <cstring> #include <queue> #include <cstdlib> #include <algorithm> #include <vector> #include <iostream> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; const int maxn = 1e4 + 10; int dp[maxn]; int a[maxn]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i=0;i<=n;i++) { int mxx = 0; for(int j=1;j<=k;j++) { if (i + j > n) break; mxx = max(mxx, a[i + j]); dp[i + j] = max(dp[i + j], dp[i] + j * mxx); //printf("i=%d j=%d dp[%d]=%d ", i, j, i + j, dp[i + j]); } } printf("%d ", dp[n]); return 0; }
#include <cstdio> #include <cstring> #include <queue> #include <cstdlib> #include <algorithm> #include <vector> #include <iostream> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; const int maxn = 1e4 + 10; int dp[maxn]; int a[maxn]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i=1;i<=n;i++) { int mxx = 0; for(int j=0;j<k;j++) { if (i < j + 1) break; mxx = max(mxx, a[i - j]); dp[i] = max(dp[i],dp[i - j - 1] + mxx * (j + 1)); // printf("i=%d j=%d dp[%d]=%d dp[%d]=%d ", i, j, i, dp[i],i-j,dp[i-j]); // printf("mxx=%d ", mxx); } } printf("%d ", dp[n]); return 0; }