NC54299. 能天使的愿望
描述
众所周知，能天使有两个愿望：老板……不，义人，以手中的这把铳起誓，我将守护您的生命直到万物终结之日。
第一个愿望！请送我八把铳当礼物！我们天使都有自己的守护铳，但只有一把可不够看！你显然不能帮能天使实现第二个愿望，但是你可以用你手上的龙门币帮她完成第一个愿望
第二个愿望……找个人把我头上的这盏日光灯管关掉！
输入描述
第一行 4 个整数，N,M,K,Y第二行 N 个整数，第 i 个数表示 ai接下来 N 行，每行 M 个数，表示 Pi,j
输出描述
一行一个非负整数，表示题目描述中的最小花费
示例1
输入:
5 8 10 3 10 20 100 5 1 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 16 1 2 3 4 5 6 7 8 1 3 6 10 15 21 28 36 10 20 30 40 50 60 70 80
输出:
12
说明:
在样例1中，在第三家店买7把铳，然后在第一家买3把铳，总价为7+5=12，因为都是3把以上，所以不用邮费示例2
输入:
5 8 10 8 10 20 100 5 1 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 16 1 2 3 4 5 6 7 8 1 3 6 10 15 21 28 36 10 20 30 40 50 60 70 80
输出:
21
说明:
在样例2中，在第三家店买8把铳，然后在第四家店买2把，总价为8+3+2*5=21，其中2*5为在第四家店购买的邮费C++14(g++5.4) 解法, 执行用时: 507ms, 内存消耗: 5472K, 提交时间: 2019-11-22 21:35:31
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
long long a[maxn],b[maxn];
long long f[maxn];
int main()
{
ios::sync_with_stdio(0);
int n,k,y,m;
cin>>n>>m>>k>>y;
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>b[j];
if(j<y) b[j]+=a[i]*j;
}
for(int j=k;j>=1;j--)
{
for(int l=1;l<=min(j,m);l++)
{
f[j]=min(f[j],f[j-l]+b[l]);
}
}
}
cout<<f[k]<<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 626ms, 内存消耗: 2936K, 提交时间: 2020-05-02 11:33:51
#include<bits/stdc++.h>
using namespace std;
int a[10005],p[10005],ans[805*805];
int main()
{
memset(ans,0x3f,sizeof(ans));
ans[0]=0;
int n,m,k,y;
cin>>n>>m>>k>>y;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>p[j];
if(j<y) p[j]+=a[i]*j;
}
for(int j=k;j>=0;j--)
for(int l=1;l<=m&&l<=j;l++)
ans[j]=min(ans[j],ans[j-l]+p[l]);
}
cout<<ans[k];
}