第6回ブルーブリッジ杯決勝問題:住民集会
7116 ワード
タイトル:
:
, L, , i di。
, 。 , , 4 , 3 ,1 。
, ti 。
di ti, :p1, p2, p3, p4 (p1<=p2<=p3<=p4=L), 。
【 】
n, L, 。
n , di, ti, i 。
【 】
, , 。
【 】
6 10
1 3
2 2
4 5
5 20
6 5
8 7
【 】
18
【 】
2, 5, 8, 10 4 ,6 1, 0, 1, 0, 2, 0, 1*3+0*2+1*5+0*20+2*5+0*7=18。
【 】
10% ,1<=n<=300。
30% ,1<=n<=2000,1<=L<=10000,0<=di<=L,di<=di+1,0<=ti<=20。
100% ,1<=n<=100000,1<=L<=1000000,0<=di<=L,di<=di+1,0<=ti<=1000000。
:
< 512M
CPU < 5000ms
, :“ ...” 。
, , 。
: main 0
: ANSI C/ANSI C++ , 。
: #include , 。
, 。
参考まで//
#include
using namespace std;
int N, L;
int d[100001], t[100001];
int R[1000001];
bool vis[1000001];
int M(3);
int chose[4];
int xchose[4];
set<long> cset;
void init()
{
cin >> N >> L;
for(int i=0; icin >> d[i] >> t[i];
}
for(int i=0; i<=L; ++i) {
R[i] = i;
}
memset(vis,false,sizeof(bool)*1000001);
chose[3] = L;
}
long getCost(int i)
{
//
int td = d[i], tt = t[i];
for(int j=0; j<4; ++j) {
if(td>chose[j]) continue;
return (chose[j]-td)*tt;
}
return (L-td)*tt;
}
void process()
{
// , ,
long cost(0);
copy(chose,chose+4,xchose);
sort(xchose,xchose+4);
for(int i=0; ilong tcost = getCost(i);
cost += tcost;
}
cset.insert(cost);
}
void dfs(int m)
{
if(m==0) {
process();
} else {
for(int i=0; iif(!vis[i]) {
chose[M-m] = R[i];
vis[i] = true;
dfs(m-1);
vis[i] = false;
}
}
}
}
int main()
{
init();
dfs(3);
cout << *cset.begin();
return 0;
}