CodeForces - 1625C
2024-10-21 03:32:50
题意: 一条马路,有n个限速牌,表示的是从这个限速牌开始到下一个限速牌或者到马路尾的这段距离的速度,你可以拆除其中k个限速牌,问最少的时间是多少。
题解: 线性问题,每个牌拆和不拆两种情况,开始考虑的贪心,但不会。
dp[i][j]表示的是到i这个点,一共拆除了j个限速牌。
可以根据限速牌数量写状态转移方程: dp[pos][j+pos-i-1]=min(dp[pos][j+pos-i-1],dp[i][j]+(a[pos]-a[i])*b[i]);
其中pos 和 i 是遍历的先后两个点,pos-i-1的意思是将pos 和 i中的牌子拆掉。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=505;
const ll inf=1e18;
ll a[N],b[N],dp[N][N];
ll vis[N],ans,sum[N];
ll n,m,k;
signed main(){
cin>>n>>m>>k;
for(ll i=1;i<=n;i++) cin>>a[i];
for(ll i=1;i<=n;i++) cin>>b[i];
a[n+1]=m;
memset(dp,0x3f,sizeof(dp));
dp[1][0]=0;
for(ll i=1;i<=n;i++) dp[i+1][0]=dp[i][0]+(a[i+1]-a[i])*b[i];//初始化,一个牌子不拆的情况下,到每一个点花费的时间
for(ll i=1;i<=n;i++)
for(ll j=0;j<=k;j++)
for(ll z=i+1;z<=n+1;z++){
dp[z][j+z-i-1]=min(dp[z][j+z-i-1],dp[i][j]+(a[z]-a[i])*b[i]);
}
ll ans=inf;
for(ll i=0;i<=k;i++) ans=min(ans,dp[n+1][i]);
cout<<ans<<endl;
}
最新文章
- Linux:-杀进程的技巧
- smarty 模板的入门使用
- 用字符串模拟两个大数相加——java实现
- android 使用WebView 支持播放优酷视频,土豆视频
- YouTube上的版权保护
- oracle where 后面的条件中|| 是什么意思
- Sublime text3 笔记
- [置顶] 请听一个故事------>;你真的认为iPhone只是一部手机?苹果惊天秘密!!
- MVC自定义AuthorizeAttribute实现权限管理
- 安卓的sqlite增删改
- C#对html的操作
- 通过SDK和API获取阿里云RDS的监控数据
- 如何管理Session(防止恶意共享账号)——理论篇
- git reset揭秘
- CSS3_伸缩盒模型_弹性布局_等分布局_flex 布局
- 静态文件link 数据库迁移命令 新建app命令
- shelly - HYMN TO INTELLECTUAL BEAUTY
- tabindex 属性
- 对于Redis的了解
- Mysql 5.6 慢日志配制