pku 3413 rpg的任务和经验问题.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 3413 RPG的任务和经验问题
//#define NMAX 
//#define INFI 
#define PI 3.1415926
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back
#define NMAX 12

bool visited[NMAX];
int num;
double a[NMAX];
double b[NMAX];
double s[NMAX];
double ans;
int xulie[NMAX];
int tempxu[NMAX];

double gailv(double aa,double bb,double xp)
{
    if(xp<=aa) return 0.00;
    else if(xp>=bb) return 1.00;
    else return (xp-aa)/(bb-aa);
}

void search(int i,double xp,double gv,int count)
{
    int j;
    count++;
 visited[i]=true;
 tempxu[count]=i;
// printf("count=%d i=%d xp=%.3f \n",count,i,xp);
//  for(j=1;j<=num;j++) printf(" %d",visited[j]);
//  printf("\n");
 if(count==num && ans<gv*gailv(a[i],b[i],xp)) 
 {
     ans=gv*gailv(a[i],b[i],xp);
 //   printf("go ");
 //    printf("ans=%.3f   ",ans);
     for(j=1;j<=count;j++) 
     {xulie[j]=tempxu[j];
 //    printf(" %d",tempxu[j]);
     }
 //        printf("\n");
     return;
 }
 gv=gv*gailv(a[i],b[i],xp);
 xp+=s[i];
// printf("next gv=%.3f xp=%.3f\n",gv,xp);
 for(j=1;j<=num;j++)
 {
     if(visited[j]==false && gv*gailv(a[j],b[j],xp)>ans)
     {
        search(j,xp,gv,count);
       visited[j]=false;      
     }
 }
}

void solve(double xp)
{
    int i;
    ans=0.0;
    for(i=1;i<=num;i++)
    {
        visited[i]=false;
        xulie[i]=i;
    } 
    for(i=1;i<=num;i++) 
    {
        if(xp>a[i])
        {
            search(i,xp,1.00,0);
            visited[i]=false;
        }
    }
    printf("%.3f\n",ans);
    for(i=1;i<=num;i++) printf("%d ",xulie[i]);
    printf("\n");
}

int main()
{
    int i;
    double xp;
    scanf("%d %lf",&num,&xp);
    for(i=1;i<=num;i++)
    {
        scanf("%lf %lf %lf",&a[i],&b[i],&s[i]);
    }
    solve(xp);
}