正能量网站免费进入无需下载,曲周县建设局网站,深圳市交易中心,赣州网站建设服务GYM101002C - Greetings! 做法#xff1a;\(dp[i][S]\)表示用了\(i\)种信封#xff0c;明信片的状态为\(S\)时的最小花费#xff0c;预处理\(A[S]\)表示可以装的对应明信片的集合的花费, \(dp[i][s] min(dp[i-1][s-s2] A[s2]), s2 \in s\)。注意枚举所有子集#xff0c;再… GYM101002C - Greetings! 做法\(dp[i][S]\)表示用了\(i\)种信封明信片的状态为\(S\)时的最小花费预处理\(A[S]\)表示可以装的对应明信片的集合的花费, \(dp[i][s] min(dp[i-1][s-s2] A[s2]), s2 \in s\)。注意枚举所有子集再对每个子集枚举他们的子集复杂度是\(O(3^n)\)证明就是 \(O(\sum_{i0}^n C_n^i 2^i) O(\sum_{i0}^n C_n^i 2^i 1^{n-i}) O((21)^n) O(3^n)\) ...学到了 #include bits/stdc.h
#define pb push_back
typedef long long ll;
const int N 20;
const ll inf 0x3f3f3f3f3f3f3f;
using namespace std;
int n,k;
ll w[N], h[N], q[N];
struct node{ll w,h,c;
}A[(116)];
ll dp[N][(116)];
ll min(ll a,ll b) {if(a-1) return b;if(b-1) return a;if(ab) return a;return b;
}
int main() {scanf(%d%d,n,k);for(int i 0; i n ; i) scanf(%lld%lld%lld,w[i],h[i],q[i]);for(int st 0; st (1n); st) {ll tmp 0, num 0;A[st].w A[st].h 0;for(int i 0; i n; i) if(st(1i)) {A[st].w max(A[st].w, w[i]);A[st].h max(A[st].h, h[i]);tmp w[i]*h[i]*q[i];num q[i];}A[st].c A[st].w*A[st].h*num - tmp;}memset(dp,-1,sizeof(dp));dp[0][0] 0;for(int i 1; i k; i) {for(int st 0; st (1n); st) {ll tmp -1;for(int st2 st; st2; st2(st2-1)st) if(dp[i-1][st-st2]!-1) {tmp min(dp[i-1][st-st2] A[st2].c,tmp);}dp[i][st] tmp;}}ll ans -1;for(int i 1; i k; i) ans min(ans, dp[i][(1n)-1]);printf(%lld\n,ans);return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9737678.html
