类似背包问题,对NO2有15种状态,在每个状态有使用和不使用两种情况,分别考虑。特别注意在状态14时,即2哥NO2+80%能量,要单独判断
所以状态方程很容易就出来了,具体见代码。
#include <stdio.h>
//using namespace std;
#define N 105
#define E 15
#define INF 1 << 28
int main()
{
//freopen("in", "r", stdin);
int n, l;
int a[N], b[N], e[2][E];
while(~scanf("%d %d", &n, &l))
{
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
for(int i = 0; i < n; i++)
scanf("%d", &b[i]);
e[0][0] = 0;
for(int i = 1; i < E; i++)
{
e[0][i] = INF;
}
for(int k = 0; k < l; k++)
{
for(int i = 0; i < n; i++)
{
e[1][0] = INF;
for(int j = 0; j < E; j++)
{
e[1][j + 1] = e[0][j] + a[i];
if(j > 4 && e[0][j] + b[i] < e[1][j - 5])
{
e[1][j - 5] = e[0][j] + b[i];
}
}
if(e[0][E - 1] + b[i] < e[1][E - 6])
{
e[1][E - 6] = e[0][E - 1] + b[i];
}
if(e[0][E - 1] + a[i] < e[1][E - 5])
{
e[1][E - 5] = e[0][E - 1] + a[i];
}
for(int j = 0; j < E; j++)
{
e[0][j] = e[1][j];
}
}
}
int ans = INF;
for(int i = 0; i < E; i++)
{
if(e[0][i] < ans) ans = e[0][i];
}
printf("%d\n", ans);
}
return 0;
}