这道题虽然标签式dp但我只会dfs

问题 K: 公路乘车

题目描述

一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如样例的第一行就是一个费用的单子。

没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<=n<=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。

输入 第一行十个整数分别表示行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。

第二行一个整数n表示，旅客的总路程数。

输出

仅一个整数表示最少费用。 样例输入 12 21 31 40 49 58 69 79 90 101 15 样例输出 147

WA CODE

#include<bits/stdc++.h>
#define INF 100000000
using namespace std;
const int N=105;
int n,a[N],lc,ans,tot[N];
void dfs(int x)
{
	if(x>=lc)
	{
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			sum+=tot[i]*a[i];
			tot[i]=0;
		}
		ans=min(ans,sum);
		return ;
	}
    for(int i=1;i<=n;i++)
    {
    	tot[i]++;
    	dfs(x+i);
	}
}
int main()
{
	n=10,ans=INF;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	cin>>lc;
	dfs(0);
	cout<<ans;
}