解题思路:自顶而下搜索最小值
注意事项:记录答案防止时间爆炸
参考代码:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long i64;
typedef int i32;
typedef long double ld;
i64 dp[1200];
int a[11];
i64 like(int n)
{
if(n==0)
return 0; //搜索结束边界
if(n<0)
return 9999999999999; //小于0返回正无穷
if(dp[n]<12345643)
return dp[n]; //搜过了就不用再搜索了
for(int i=1;i<=10;i++)
dp[n]=min(dp[n],like(n-i)+a[i]); //比较
return dp[n];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
memset(dp,0xf,sizeof(dp)); //初始化为极大值
for(int i=1;i<=10;i++)
cin>>a[i];
int n;
cin>>n;
cout<<like(n);
return 0;
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:759 |
成绩转换 (C语言代码)浏览:1010 |
简单的a+b (C语言代码)浏览:531 |
【偶数求和】 (C语言代码)浏览:647 |
WU-格式化数据输出 (C++代码)浏览:1212 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:350 |
Cylinder (C语言描述,蓝桥杯)浏览:1247 |
模拟计算器 (C++代码)浏览:807 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:459 |
A+B for Input-Output Practice (II) (C语言代码)浏览:601 |