Bài toán
Có thể đơn giản hiểu bài toán rằng: Với một mảng vuông với chiều dài cạnh là n. Chọn ra n ô mà có hàng phân biệt, cột phân biệt mà có tích lớn nhất.
Input
Dòng 1 chứa số n. n dòng sau mỗi dòng n số mô tả mảng. Các phần tử của mảng là giá trị phần trăm, nằm trong khoảng 0.0 đến 100.0 (Chú ý đây là mảng số thực, và đây là các giá trị phần trăm). Ví dụ số 80.0 thì bạn có thể hiểu đây là 80% tức 0.8.
Output
In ra tích lớn nhất tìm được dưới dạng phần trăm. Ví dụ như số 0.9876 thì bạn in ra là 98.76. Bài toán chấp nhận sai số 1e-6.
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
bool maximize(double &a, double b){ if (a<b) a=b; else return false; return true; }
int n;
double a[123][123];
double F[21][1230997];
int FF[21][1230997];
double f(int pos, int bit){
if (pos==n+1) return 1.0;
if (FF[pos][bit]++) return F[pos][bit];
double r = 0;
int current = bit;
for (;;){
int i = __builtin_ffs(~current);
if (i>n) break;
maximize(r, f(pos+1, bit|(1<<i-1)) * a[pos][i]);
current |= (1<<i-1);
}
//for (int i=1; i<=n; i++)
//if (!((1<<i-1) & bit))
//maximize(r, f(pos+1, bit|(1<<i-1)) * a[pos][i]);
//printf("f(%d, %d) = %lf\n", pos, bit, r);
return F[pos][bit] = r;
}
main(){
int i, j;
scanf("%d", &n);
for (i=1; i<=n; i++)
for (j=1; j<=n; j++){
scanf("%lf", &a[i][j]);
a[i][j] /= 100.0;
}
printf("%.12lf\n", f(1, 0)*100);
}
Nhận xét
Ở đây mình dùng hàm __builtin_ffs để tăng tốc chương trình. Với code ban đầu, máy 2.2GHz, TL 1s, cho kết quả time limit 1 trên 20 test.
Mô tả
double f(int pos, int bit)
Đang đứng tại dòng pos, cần chọn một trong n giá trị ở dòng này. bit là dãy bit chứa các phần tử đã sử dụng.
Các lỗi thường gặp
Time limit
- Để đạt tốc độ tối ưu thì code dưới đây cần được thay thế bằng việc sử dụng __builtin_ffs.
for (int i=1; i<=n; i++)
if (!((1<<i-1) & bit))
maximize(r, f(pos+1, bit|(1<<i-1)) * a[pos][i]);
Wrong answer
- Do bạn dùng kiểu float để tính toán. Hãy sử dụng kiểu double.