2 条题解
-
2
注意注意：这道题数值很大，请不要为了节省内存而运用vector（因为最后一个如果用标准输入输出流cout、cin可达到998ms）建议用c语言。
我是被害了好几次了思路
如果只有两天，那就是一个完全背包问题，体积是第一天的价格，价值是第二天的价格。不过有很多天，所以是相邻两天做一次完全背包。
代码
#include <stdio.h> #include <string.h> inline int max(register int a,register int b){ return a>b?a:b; } int main(void){ register int s,d,m; scanf("%d%d%d",&s,&d,&m); register int f[500001]; register int a[51][11]; for(register int i=1;i<=s;i++) for(register int j=1;j<=d;j++) scanf("%d",&a[i][j]); for(register int k=2;k<=d;k++){ memset(f,0,sizeof(f)); for(register int i=1;i<=s;i++) for(register int j=a[i][k-1];j<=m;j++) f[j]=max(f[j],f[j-a[i][k-1]]+a[i][k]-a[i][k-1]); m+=f[m]; } printf("%d",m); return 0; } //已AC，最后一项510ms-
hetao1394742
@ 2024-4-21 16:36:20
给部分代码加些讲解（不一定专业，文后附有一些网上的部分关键字讲解，可以参考一下）
inline函数，人话来说，就是把
inline int po(int a){ return a * a; } int main(){ //此处省略114514字 cout << po(a); }这样的代码变成这个样子
int main(){ //此处省略114514字 cout << a * a; }可以节省时间
register int就是使用cpu内部寄存器（寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件）的变量，而平时的int是把变量放在内存中，存到寄存器中可以加快变量的读写速度大概就这么点东西，反正都是节省时间用的
-
hetao4582353 @ 2024-5-19 18:41:41
呃，这
#include <bits/stdc++.h> using namespace std; int m,s,d,f[1000000],a[50][50]; int main() { cin >> s >> d >> m; for (int i = 1;i <= s;i++) { for (int j = 1;j <= d;j++) { cin >> a[j][i]; } } for (int i = 1;i < d;i++) { memset(f,0,sizeof(f)); for (int j = 1;j <= s;j++) { for (int k = a[i][j];k <= m;k++) { f[k] = max(f[k],f[k - a[i][j]] + a[i+1][j] - a[i][j]); } } m += f[m]; } cout << m; return 0; } /* | #13 | **Accepted**8 | 98ms | | ----- | ---------------- | ------ |*/为什么我正常代码才98ms这么点
-
-
1
假设只有两天，那么相当于完全背包问题，体积是第一天的价格，价值是第二天的价格。而如果有d天，则相当于每相邻两天做一次完全背包，一共d-1次。
核心代码
for (int i = 2; i <= d; i++) { maxx = -1; memset(f, 0, sizeof(f)); for (int j = 1; j <= s; j++) for (int k = v[j][i - 1]; k <= m; k++) { f[k] = max(f[k], f[k - v[j][i - 1]] + v[j][i] - v[j][i - 1]); maxx = max(maxx, f[k]); } m += maxx; } cout << m;
hetao24883491
LV 10
@ 2023-11-4 18:51:56
- 1