DP+

P1258

想过这种思路但是觉得不可行所以只要有想法就要积极去实现！

状转

输入f[1-10]

f[i]=min{f[j]+f[i-j]}    i:[2,n)    j:[1,i);

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,a[11],f[110];

void init()

{

memset(f,10...

P1258

想过这种思路但是觉得不可行所以只要有想法就要积极去实现！

状转

输入f[1-10]

f[i]=min{f[j]+f[i-j]}    i:[2,n)    j:[1,i);

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,a[11],f[110];

void init()

{

memset(f,10,sizeof(f));

for(int i=1;i<=10;i++)

{

cin>>a[i];

f[i]=a[i];

}

cin>>n;

}

void work()

{

for(int i=2;i<=n;i++)

for(int j=1;j<i;j++)

if(f[j]+f[i-j]<f[i])

f[i]=f[j]+f[i-j];

cout<<f[n]<<endl;

}

int main()

{

init();

work();

return 0;

}