1 条题解

  • 1
    @ 2025-7-3 11:02:57
    DPDP
    #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
    上传者