这个题就是一个贪心问题,具体分析:

要使罚款最少，我们显然应尽量完成c[i]值较大的工作。 此时，我们可以将工作按c[i]从大到小进行排序，然后按照排好的顺序依次对工作进行安排，安排的规则为：使处理工作i的时间既在t[i]之内，又尽量靠后；如果t[i]之内的时间都已经排满，就放弃处理此项工作。

证明:

假设按照上述方法得到的解不是最优的，那么必然存在某个工作j应当安排到处理的过程中，却没有得到安排。假设我们要将该工作安排进去，由于时间t[j]内都已经排满，就必然需要将一个已安排的工作k与之替换，而c[k]>=c[j]，这样替换显然会增加罚款的数额。因此，除上述安排方法以外的安排方法都不会使罚款的数额减少，可得上述方法得到的结果是最优的。

 

思想就是类似于克鲁斯凯尔的最短路问题,证明也是这样.

 

具体代码:

#include<algorithm>

#include<cstdio>

using namespace std;

struct WORK{

　　int cost,time;

}work[501];

int n,m;

bool t[501];

bool COMP(WORK a,WORK b){return a.cost>b.cost;}

int main(){

　　scanf("%d %d",&m,&n);

　　for(int i=1;i<=n;i++)

　　　　scanf("%d",&work[i].time);

　　for(int i=1;i<=n;i++)

　　　　scanf("%d",&work[i].cost);

　　sort(work+1,work+n+1,COMP);

　　for(int i=1;i<=n;i++){

　　　　m-=work[i].cost;

　　　　for(int j=work[i].time;j>=1;j--)

　　　　　　if(t[j]==0){

　　　　　　　　t[j]=1;

　　　　　　　　m+=work[i].cost;

　　　　　　　　j=0;

　　　　　　}

　　}

　　printf("%d",m);

　　return 0;

}