思路:和背包长得像,那么我们就往背包上想,dp[i][j]表示前i天我们买了j个糖果的最小花费,dp[i][j]可由dp[i-1][k]转移得到,那么怎么转移?j的范围要<=min(n,im)k就最小从i-1个糖果开始(再小就不符合题意)最大到min(j,min(n,(i-1)*m))当第i-1天的k个糖果取到第i天的j个糖果就需要加上此时在第i天买糖果的花费就是+前(j-k)个糖果的价格(我们用前缀和去维护),再加上(j-k)的平方。得到dp方程为dp[i][j]=min(dp[i][j],dp[i-1][k]+a[i][j-k]+(j-k)(j-k));
#include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<queue> //#include<bits/stdc++.h> using namespace std; typedef long long ll; #define SIS std::ios::sync_with_stdio(false) #define space putchar(' ') #define enter putchar('\n') #define lson root<<1 #define rson root<<1|1 typedef pair<int,int> PII; const int mod=1e9+7; const int N=2e6+10; const int M=2e3+10; const int inf=0x7f7f7f7f; const int maxx=2e5+7; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } ll lcm(ll a,ll b) { return a*(b/gcd(a,b)); } template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar('0' + x % 10); } ll qsm(int a,int b,int p) { ll res=1%p; while(b) { if(b&1) res=res*a%p; a=1ll*a*a%p; b>>=1; } return res; } int n,m; int dp[310][310],a[310][310]; int main() { cin>>n>>m; memset(dp,inf,sizeof dp); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } sort(a[i]+1,a[i]+1+m); for(int j=1;j<=m;j++) a[i][j]+=a[i][j-1]; } // for(int i=1;i<=n;i++) dp[0][0]=0; for(int i=1;i<=n;i++) { for(int j=i;j<=min(n,i*m);j++) { for(int k=i-1;k<=min(n,min(j,(i-1)*m));k++) { dp[i][j]=min(dp[i][j],dp[i-1][k]+a[i][j-k]+(j-k)*(j-k)); } } } cout<<dp[n][n]<<endl; return 0; } /* 1 3 2 1 1 2 3 4 1 0 1 2 3 2 1 2 3 4 */