织梦学校网站,商丘建网站,一般注册公司要多少钱,织梦网站代码传送门#xff1a; 题目
dp[i][j][k] 表示 考虑到第i个数 计算前j个数的和 进行了k次操作
则有 若不把第i个数放入前j个数中 dp[i][j][k] dp[i-1][j][k] 若把第i个数放入前j个数中 至少需要把第i个移到第j个#xff0c;即进行i-j次操作if(k i-j) dp[i][j][k…传送门 题目
dp[i][j][k] 表示 考虑到第i个数 计算前j个数的和 进行了k次操作
则有 若不把第i个数放入前j个数中 dp[i][j][k] dp[i-1][j][k] 若把第i个数放入前j个数中 至少需要把第i个移到第j个即进行i-j次操作if(k i-j) dp[i][j][k] dp[i-1][j-1][k-(i-j)] 然而如果直接开数组则要开dp[151][151][151*151]这么大 这显然是不可取的
又因为 dp[i][ ][ ] 始终只和 dp[i-1][ ][ ] 有关所以考虑滚动数组
即用 dp[i%2][ ][ ] 表示 dp[i][ ][ ]
话不多说上代码
#includeiostream
#includecstdio
#includecstring
using namespace std;
typedef long long ll;
const int inf0x3f3f3f3f;
int N,K,S;
ll dp[2][155][155*155];
ll a[155];
int main(){scanf(%d%d%d,N,K,S);for(int i1;iN;i)scanf(%d,a[i]);memset(dp,inf,sizeof(dp));dp[0][0][0]0;for(int i1;iN;i){memset(dp[i%2][0],0,sizeof(dp[i%2][0]));for(int j1;ji;j){for(int k0;ki*j;k){dp[i%2][j][k]dp[(i-1)%2][j][k];if(ki-j)dp[i%2][j][k]min(dp[i%2][j][k],dp[(i-1)%2][j-1][k-(i-j)]a[i]);}}}ll ansinf;for(int k0;kmin(S,N*(N-1)/2);k)ansmin(dp[N%2][K][k],ans);printf(%lld\n,ans);return 0;
}
