记录编号	317231	评测结果	AAAAAAAAAAAA
题目名称	[USACO] “破锣摇滚”乐队	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-10-07 19:41:49	内存使用	0.40 MiB

#include<cstdio>
#include<queue>
using namespace std;
int a[30];
bool vis[30][30][30];
int dis[30][30][30];
struct node{
    int i,j,r,d;//考虑了前i,录制j个,剩余r分钟时，距离d为使用的最少唱片数 
    node(int _i,int _j,int _r,int _d){
        i=_i;j=_j;r=_r;d=_d;
    }
    bool operator <(const node &B)const{
        return d>B.d;
    }
};
int n,m,t;
void dijkstra(){
    priority_queue<node> q;
    q.push(node(0,0,0,0));
    while(!q.empty()){
        node tmp=q.top();q.pop();
        if(vis[tmp.i][tmp.j][tmp.r])continue;
        vis[tmp.i][tmp.j][tmp.r]=1;
        dis[tmp.i][tmp.j][tmp.r]=tmp.d;
        if(tmp.i<n){
            if(!vis[tmp.i+1][tmp.j][tmp.r])q.push(node(tmp.i+1,tmp.j,tmp.r,tmp.d));
            if(tmp.r>=a[tmp.i+1]&&!vis[tmp.i+1][tmp.j+1][tmp.r-a[tmp.i+1]])q.push(node(tmp.i+1,tmp.j+1,tmp.r-a[tmp.i+1],tmp.d));
            if(tmp.d<m&&a[tmp.i+1]<=t&&!vis[tmp.i+1][tmp.j+1][t-a[tmp.i+1]])q.push(node(tmp.i+1,tmp.j+1,t-a[tmp.i+1],tmp.d+1));
        }
    }
} 
int main(){
    freopen("rockers.in","r",stdin);
    freopen("rockers.out","w",stdout);
    scanf("%d%d%d",&n,&t,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
    }
    dijkstra();
    int ans=0;
    
    for(int i=0;i<=t;++i){
         for(int j=0;j<=n;++j){
            if(vis[n][j][i]&&dis[n][j][i]<=m&&j>ans)ans=j;
         }  
    }
    printf("%d\n",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}