当前位置:网站首页>Poj-3486-computers[dynamic planning]
Poj-3486-computers[dynamic planning]
2022-07-01 02:46:00 【JackDawn!?】
The original title is
The main idea of the topic
One should ensure that he is n Computers are available every year in the middle of the year , He has two choices every year , Or buy a new computer , Or repair the computer you used before . The money for a new computer is fixed , The money for repairing the computer is m[y][z],y Is the year the computer was purchased ,z Is the year of repair . It is required to find the minimum cost .
Ideas
set up dp[i]
Before presentation i There is money needed for computers to be available every year , Put it first j A new computer was replaced in (1<=j<=i), Then the state transition equation is obtained
dp[i] = min(dp[j-1]+c+m[j][i]) (1<=j<=i)
Through this O(n^2) The answer can be obtained through the program of .
AC Code
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1005;
int c, y;
int m[maxn][maxn];
int dp[maxn];
int main(void)
{
while(~scanf("%d", &c)) {
scanf("%d", &y);
for(int i = 1; i <= y; ++i) {
for(int j = i; j <= y; ++j) {
scanf("%d", &m[i][j]);
}
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= y; ++i) {
for(int j = 1; j <= i; ++j) {
dp[i] = min(dp[i], dp[j-1]+c+m[j][i]);
}
}
printf("%d\n", dp[y]);
}
return 0;
}
边栏推荐
- 如何在智汀中實現智能鎖與燈、智能窗簾電機場景聯動?
- import tensorflow.contrib.slim as slim报错
- Here comes the share creators budding talent training program!
- Gartner研究:在中国,混合云的采用已成为主流趋势
- Evaluation of the entry-level models of 5 mainstream smart speakers: apple, Xiaomi, Huawei, tmall, Xiaodu, who is better?
- js 找出两个数组中的重复元素
- lavaweb【初识后续问题的解决】
- AI edge computing platform - beaglebone AI 64 introduction
- PTA 1016
- servlet【初识】
猜你喜欢
如何在智汀中實現智能鎖與燈、智能窗簾電機場景聯動?
The latest wechat iPad protocol code obtains official account authorization, etc
Comment réaliser la liaison entre la serrure intelligente et la lampe, la scène du moteur de rideau intelligent dans le timing intelligent?
Lenovo x86 server restart management controller (xclarity controller) or TSM method
Restcloud ETL practice to realize incremental data synchronization without identification bit
基于Pytorch完整的训练一个神经网络并进行验证
RestCloud ETL WebService数据同步到本地
MnasNet学习笔记
RestCloud ETL实践之无标识位实现增量数据同步
LabVIEW calculates the camera image sensor resolution and lens focal length
随机推荐
最新微信ipad协议 CODE获取 公众号授权等
ssh配置免密登录时报错:/usr/bin/ssh-copy-id: ERROR: No identities found 解决方法
php批量excel转word
Densenet network paper learning notes
Dell server restart Idrac method
鼠标悬停效果四
Comment réaliser la liaison entre la serrure intelligente et la lampe, la scène du moteur de rideau intelligent dans le timing intelligent?
Image preloading in JS
SWT / anr problem - storagemanagerservice stuck
Contrastive learning of Class-agnostic Activation Map for Weakly Supervised Object Localization and
5款主流智能音箱入门款测评:苹果小米华为天猫小度,谁的表现更胜一筹?
在国内如何买港股的股?用什么平台安全一些?
Small program cloud development -- wechat official account article collection
查看 jvm 参数
Lenovo x86 server restart management controller (xclarity controller) or TSM method
[2022] Jiangxi postgraduate mathematical modeling scheme and code
Desai wisdom number - other charts (parallel coordinate chart): employment of fresh majors in 2021
使用ipmitool配置X86服务器的BMC网络和用户信息
Optimal transport Series 1
C language a little bit (may increase in the future)