luogu P3399 丝绸之路
analysis
本人表示非常兴奋,毕竟这是我第一个没有看题解自己推出来的方程:
其中
code
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define min(a,b) ((a>b)?b:a)
int n,m;
const int maxn=1000,maxm=1000;
int D[maxn];
int C[maxm];
int f[maxn][maxm];
inline int read()
{
int _ans=0;bool _neg=false;char _r=getchar();
while(_r>'9'||_r<'0'){if(_r=='-')_neg=true;_r=getchar();}
while(_r>='0'&&_r<='9'){_ans=_ans*10+_r-'0';_r=getchar();}
return (_neg)?-_ans:_ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("datain.txt","r",stdin);
#endif
n=read();
m=read();
clean(f,0x7f);
clean(f[0],0);
loop(i,1,n)D[i]=read();
loop(i,1,m)C[i]=read();
loop(i,1,n)
{
loop(j,i,m)
{
loop(k,j-m,j+1-i)
{
if(k<=0)continue;
f[i][j]=min(f[i][j],f[i-1][j-k]+D[i]*C[j-k+1]);
}
}
}
int res=INT_MAX;
loop(i,n,m)res=min(res,f[n][i]);
printf("%d",res);
return 0;
}