满减 HRBUST - 2455
2024-09-05 18:33:40
https://vjudge.net/problem/HRBUST-2455
有两种优惠方式,一是满400减100,另外一种是商品自带折扣,二者不可叠加
dp[i][j]表示前i种商品,(参与满400减100活动的商品价格之和)%400 == j 的最少总花费,这里默认后面的商品都使用自身折扣,
为了避免小数,把价格A[i]都扩大十倍A[i]*=10。
容易得到转移方程 dp[i][j] = min(dp[i-1][x]+j*10+(x+A[i]/10)/400*3000-x*10-A[i]/10*B[i],dp[i-1][j])
其中 x = (j-A[i]+1200)%400
边界dp[0][0]表示所有商品只使用自身折扣
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int t;
int N;
int A[];
int B[];
int dp[][];
double ans =0.0;
const int INF = 1e18;
signed main()
{
scanf("%lld",&t);
while(t--){
int tmp =;
scanf("%lld",&N);
for(int i=;i<=N;i++){
scanf("%lld%lld",&A[i],&B[i]);
tmp+=A[i]*B[i];
A[i]*=;
for(int j=;j<;j++){
dp[][j]=dp[i][j]=INF;
}
}
dp[][]=tmp;
int x ;
for(int i=;i<=N;i++){
for(int j=;j<;j++){
x= (j-A[i]/+)%;
dp[i][j]=min(dp[i-][x]-(A[i]/10ll)*B[i]+j*10ll-x*10ll+((x+A[i]/10ll)/400ll)*3000ll,dp[i-][j]);
}
} tmp = 1e18;
for(int j=;j<;j++){
tmp = min(tmp,dp[N][j]);
} printf("%.1f\n",tmp*0.1); } }
最新文章
- [Excel] 打印设置
- C#压缩图片——高质量压缩方式
- RPC 框架通信原理
- vb 和vb.net的区别
- 【转】为什么我说 Android 很糟糕
- 【转】《APUE》第三章笔记(4)及习题3-2
- 关于AsyncTask 的退出
- hdu 2553 N皇后问题 (经典DFS)
- lighttpd 介绍及安装
- [bzoj4822][Cqoi2017]老C的任务&;[bzoj1935][Shoi2007]Tree 园丁的烦恼
- 2018-2019-2 20165221『网络对抗技术』Exp4:恶意代码分析
- 安装VS2010时出现进入的图标没有与需要部分升级VS10Sp1-KB983509的解决方案
- 新闻API接口
- (74)Wangdao.com第十三天_Object 对象_属性描述对象
- Codeforces 1080C- Masha and two friends
- SNF快速开发平台MVC-富文本控件集成了百度开源项目editor
- 算法 -- 四种方法获取的最长“回文串”,并对时间复杂进行分析对比&;PHP
- Python 5 -- 模块
- LVS持久化与超时时间问题分析
- HDU 3592 World Exhibition(线性差分约束,spfa跑最短路+判断负环)