「NOIP模拟赛」机房人民大团结
最近，机房出了一个不团结分子：Dr.Weissman。他经常欺骗同学们吃一种“教授糖豆”，使同学们神志不清，殴打他人，砸烂计算机，破坏机房团结。幸运地，一个和谐家认清了Dr.Weissman的本质。机房人民团结在一起，共同对抗Dr.Weissman及“教授糖豆”。
同学们十分具有社会责任感：他们害怕“教授糖豆”流向社会，导致动乱。于是，刚才提到的和谐家身先士卒，为了实验，品尝“教授糖豆”。
每个“教授糖豆”的性质都有所不同。同志们已经研究出每个糖豆对人的影响。具体地，每个糖豆都有一个破坏值，吃掉这颗糖豆后，身先士卒的和谐家会对机房造成一定的破坏，破坏程度为先前累积的破坏值加上本次食用糖豆的破坏值，而且这颗“教授糖豆”的破坏值会加入累积。为了减小实验造成的破坏，同学们准备了几颗“治疗糖豆“，功能是无条件将累积的“破坏值”清零。
由于实验要求，和谐家只能按照给定的顺序吃掉“教授糖豆”，但可以随时吃掉一颗或多颗“治疗糖豆”。
你能帮助和谐家同志尽量减小实验所造成的破坏吗？
「输入」
第一行，两个数，用空格，分隔开，一个n，一个m。（n，m均为正整数。）n表示“教授糖豆”的数目，m表示“治疗糖豆”的数目。
剩余n行，每行1个正整数，表示“教授糖豆”的破坏值。和谐家必须按照给定的顺序，一次一个，吃掉所有“教授糖豆”。
「输出」
一行，一个数，表示实验造成的最小破坏。
「输入样例」
3 1
1 2 3
「输出样例」
7
「数据规模」
对于100%的数据，1<=n<=100，m<=n
所有破坏值的加和小于10^9。
题解
显然二分是不可以的
应该用dp来做
f[i][j][k]表示吃了i个糖，j个药，最后一个药在吃k个糖前吃了的最小代价
转移比较简单
或者用f[i][j]表示吃了i个糖j个药，然后把药看成在糖的序列中放一些断点，预处理一下吃一段糖的代价
这个似乎更好想
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<set> #define ll long long #define inf (1LL<<60) using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; ll ans=inf,f[105][105][105],a[105],sum[105]; ll cal(int l,int r) { if(l==0)return sum[r]; return sum[r]-sum[l-1]; } int main() { //freopen("smallunion.in","r",stdin); //freopen("smallunion.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) f[i][j][k]=inf; f[0][0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<i;j++) for(int k=0;k<=i;k++) f[i][j][k]=f[i-1][j][k]+cal(k,i); for(int j=1;j<=i;j++) for(int k=0;k<i;k++) f[i][j][i]=min(f[i][j][i],f[i-1][j-1][k]+a[i]); } for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) ans=min(ans,f[n][i][j]); printf("%lld",ans); return 0; } |
OI 课件=>
