#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
//i,money,dishes
int kn(vector<vector<vector<int> > > &dp,vector<int> &cost,vector<int> &fav,int n,int k,int i,int money,int dishes){
if(i>2*k||money<=0||dishes<=0)return 0;
if(dp[i][money][dishes]!=-1)return dp[i][money][dishes];
if(cost[i]>money)return dp[i][money][dishes]=kn(dp,cost,fav,n,k,i+1,money,dishes);
return dp[i][money][dishes]=max(kn(dp,cost,fav,n,k,i+1,money,dishes),fav[i]+kn(dp,cost,fav,n,k,i+1,money-cost[i],dishes-1));
}
int main(){
int n,x,t,k;
while(cin>>n>>x>>t>>k){
if(n==0&&k==0&&x==0&&t==0)return 0;
n++;
vector<int> cost(2*k+1),fav(2*k+1);
int i=0,j,tmp;
while(i++<k){
j=0;
cin>>cost[i];
cost[i+k]=cost[i];
while(j++<n){
cin>>tmp;
fav[i]+=tmp;
}
fav[i+k]=fav[i];
}
// for(int i:cost)
// cout<<i<<' ';
int m=floor(double(x * n) / 1.1 + 1e-6) - n * t;
vector<vector<vector<int> > > dp(2*k+1,vector<vector<int> >(m+1,vector<int>(2*n+1,-1)));
double ans=kn(dp,cost,fav,n,k,1,m,2*n);
// cout<<ans<<endl;
ans/=n;
printf("%.2lf\n",ans);
// cout<<m<<endl;
}
return 0;
}
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
//i,money,dishes
int kn(vector<vector<vector<int> > > &dp,vector<int> &cost,vector<int> &fav,int n,int k,int i,int money,int dishes){
if(i>2*k||money<=0||dishes<=0)return 0;
if(dp[i][money][dishes]!=-1)return dp[i][money][dishes];
if(cost[i]>money)return dp[i][money][dishes]=kn(dp,cost,fav,n,k,i+1,money,dishes);
return dp[i][money][dishes]=max(kn(dp,cost,fav,n,k,i+1,money,dishes),fav[i]+kn(dp,cost,fav,n,k,i+1,money-cost[i],dishes-1));
}
int main(){
int n,x,t,k;
while(cin>>n>>x>>t>>k){
if(n==0&&k==0&&x==0&&t==0)return 0;
n++;
vector<int> cost(2*k+1),fav(2*k+1);
int i=0,j,tmp;
while(i++<k){
j=0;
cin>>cost[i];
cost[i+k]=cost[i];
while(j++<n){
cin>>tmp;
fav[i]+=tmp;
}
fav[i+k]=fav[i];
}
// for(int i:cost)
// cout<<i<<' ';
int m=floor(double(x * n) / 1.1 + 1e-6) - n * t;
vector<vector<vector<int> > > dp(2*k+1,vector<vector<int> >(m+1,vector<int>(2*n+1,-1)));
double ans=kn(dp,cost,fav,n,k,1,m,2*n);
// cout<<ans<<endl;
ans/=n;
printf("%.2lf\n",ans);
// cout<<m<<endl;
}
return 0;
}
Comments
Post a Comment