http://www.voidcn.com/article/p-uujpcruu-pc.html
https://blog.csdn.net/wyk1823376647/article/details/52511331
int dp[2][100011];
int main()
{
int i,n,k,pl,j,ans;
while(scanf("%d%d",&n,&k)!=EOF)
{
for (i = 1 ;i <= n; i++)
scanf("%d",&pa[i]);
memset(dp,0,sizeof(dp));
for(i = 1; i <= k; i++)
{
ans = 0x3f3f3f3f;
for( j = i ; j <= n ; j++)
{
dp[1][j] = dp[0][j-1] + pa[j] * i; //当前最优解 = 在 j 之前的最优解 + pa[j] * i;
dp[0][j-1] = ans; // 当前 j-1最优解
if(ans > dp[1][j])
ans = dp[1][j];
}
}
printf("%d\n",ans);
}
return 0;
}
给你一个长为n(10<=n<=10000)的数组,数组中的每一个数大于等于1小于等于1000000。请你找出一个长为k(100<=k<=1000)的子序列。找序列时,假如第一个数找的是数组中的第i个位置的数,那么找第二个数时只能找数组中第i个位置后的数,依次找出k个数。使得第一个数*1+第二个数*2+...+第k个数*k的值最小。
输入
有多组(小于11组)测试数据,每组第一行输入n和k(用空格隔开),第二行输入n个数(数之间用空格隔开)。
输出
请输出最小的和。
示例输入
15 5 5 4 3 2 1 1 2 3 4 5 5 4 3 2 1
示例输出
19
int main()
{
//freopen("//media/学习/ACM/input.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
int i,j;
for( dp[0][0]=0,i=1;i<=n;i++)scanf("%d",&a[i]),dp[1][i]=dp[0][i]=0;
for(i=1;i<=m;i++)
{
ans=INF;//代表j之前
for(j=i;j<=n;j++)
{
dp[1][j]=dp[0][j-1]+a[j]*i;
dp[0][j-1]=ans;
if(ans>dp[1][j])ans=dp[1][j];
}
}
printf("%lld\n",ans);
}
return 0;
}
https://blog.csdn.net/wyk1823376647/article/details/52511331
int dp[2][100011];
int main()
{
int i,n,k,pl,j,ans;
while(scanf("%d%d",&n,&k)!=EOF)
{
for (i = 1 ;i <= n; i++)
scanf("%d",&pa[i]);
memset(dp,0,sizeof(dp));
for(i = 1; i <= k; i++)
{
ans = 0x3f3f3f3f;
for( j = i ; j <= n ; j++)
{
dp[1][j] = dp[0][j-1] + pa[j] * i; //当前最优解 = 在 j 之前的最优解 + pa[j] * i;
dp[0][j-1] = ans; // 当前 j-1最优解
if(ans > dp[1][j])
ans = dp[1][j];
}
}
printf("%d\n",ans);
}
return 0;
}