1 条题解
-
1
#include<bits/stdc++.h> using namespace std; int a[15]; int n; int dp[1005]; signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); for(int i=1;i<=10;i++) cin>>a[i]; cin>>n; for(int i=1;i<=n;i++) dp[i]=1e9; for(int i=1;i<=n;i++){ for(int j=i-10;j<i;j++){ dp[i]=min(dp[i],dp[j]+a[i-j]); } } cout<<dp[n]; return 0; } /* 状态定义: dp[i]:行驶 i 公里最小乘车费用 转移方程: dp[i]=min(dp[j] (i-10 <= j <= i-1) ) +a[i-j] * a[i-j]为一次行驶的距离费用 答案: 显然为 dp[n] */
- 1
信息
- ID
- 591
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- (无)
- 递交数
- 57
- 已通过
- 32
- 上传者