跳至内容
璟雯院
珺璟如晔,雯华若锦
用户工具
登录
站点工具
搜索
工具
显示页面
修订记录
反向链接
最近更改
媒体管理器
网站地图
登录
>
最近更改
媒体管理器
网站地图
您在这里:
start
»
icpc
»
problems
»
luogup1977
icpc:problems:luogup1977
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
====== 出租车拼车 ====== ===== 想法 ===== 使用背包的思路来处理,f[i][j]为到第i辆车时,处理了j个人的最优情况,需要注意处理边界问题。 ===== 代码实现 ===== <code c++> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N = 110; int f[N][N]; int t[N], z[N], sum[N]; int main() { int n, k, d, s; scanf("%d %d %d %d", &n, &k, &d, &s); for (int i = 1; i <= k; i++) { scanf("%d %d", &t[i], &z[i]); sum[i] = sum[i - 1] + z[i]; } if (sum[k] < n) { printf("impossible"); return 0; } memset(f, 0x7f, sizeof(f)); f[0][0] = 0; for (int i = 1; i <= k; i++) for (int j = 0; j <= sum[i]; j++) { f[i][j] = f[i - 1][j]; for (int now = 1; now <= z[i] && j - now >= 0; now++) f[i][j] = min(f[i][j], f[i - 1][j - now] + d + now * t[i]); } printf("%d", f[k][n]); return 0; } </code>
/app/www/public/data/pages/icpc/problems/luogup1977.txt
· 最后更改: 2024/03/26 04:56 由
温婕莺
页面工具
显示页面
修订记录
反向链接
回到顶部