| Description |
You're in the middle of writing your newspaper's end-of-year economics summary,and you've decided that you want to show a number of charts to demonstrate howdifferent stocks have performed over the course of the last year. You've alreadydecided that you want to show the price of n different stocks, all at the same kpoints of the year.A simple chart of one stock's price would draw lines between the points (0,price0), (1, price1), ... , (k-1, pricek-1), where pricei is the price of thestock at the ith point in time.In order to save space, you have invented the concept of an overlaid chart. Anoverlaid chart is the combination of one or more simple charts, and shows theprices of multiple stocks (simply drawing a line for each one). In order to avoidconfusion between the stocks shown in a chart, the lines in an overlaid chart maynot cross or touch.Given a list of n stocks' prices at each of k time points, determine the minimumnumber of overlaid charts you need to show all of the stocks' prices. |
Input The first line of input will contain a single integer T, the number of testcases. After this will follow T test cases on different lines, each of the form:n kprice0,0 price0,1 ... price0,k-1price1,0 price1,1 ... price1,k-1...pricen-1,0 pricen-1,1 ... pricen-1,k-1Where pricei,j is an integer, the price of the ith stock at time j. |
Output For each test case, a single line containing "Case #X: Y", where X is the numberof the test-case (1-indexed) and Y is the minimum number of overlaid chartsneeded to show the prices of all of the stocks.1 ≤ T ≤ 1002 ≤ k ≤ 250 ≤ pricei,j ≤ 10000001 ≤ n ≤ 100 |
Sample Input 33 41 2 3 42 3 4 66 5 4 33 35 5 54 4 64 5 45 21 12 25 44 44 1 |
Sample Output Case #1: 2Case #2: 3Case #3: 2 |
题解：
这个题目首先，马上就可以知道那些股票可以放在一张纸上，那些不可以，那么就可以把可以放在一张纸上的点连边。
那么，我们把股票看成一个点，一条路径看成一张纸，那么这个题目就转化成了最小路径覆盖的问题，用网络流或者二分图解决。
想到这里，我发现我dinic忘了怎么打了，匈牙利也忘了，板子部分是找自己模板的，以后用dinic再打一遍吧。
代码：
#include#include #include #include #include #include #define MAXN 1000using namespace std;int cost[MAXN][MAXN];int flag[MAXN],can[MAXN][MAXN],too[MAXN];int n,k,ans;void pre(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int K=2;k<=k;K++){ if((cost[i][K]>cost[j][K])&&(cost[i][K-1]>cost[j][K-1])) break; if((cost[i][K]-cost[j][K])*(cost[i][K-1]-cost[j][K-1])<=0) break; if(K==k) can[i][j+n]=can[j+n][i]=1; }}bool dfs(int now){ for(int i=n+1;i<=n*2;i++){ if(can[now][i]&&flag[i]==0){ flag[i]=1; if(!too[i]||dfs(too[i])){ too[i]=now;return 1; } } } return 0;}int main(){ int t;cin>>t; int Case=0; while(t--){ scanf("%d%d",&n,&k); memset(cost,0,sizeof(cost)); memset(can,0,sizeof(can)); memset(too,0,sizeof(too)); memset(flag,0,sizeof(flag));ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) scanf("%d",&cost[i][j]); pre(); for(int i=1;i<=n;i++){ for(int j=n+1;j<=n*2;j++) flag[j]=0; if(dfs(i)) ans++; } printf("Case #%d: %d\n",++Case,n-ans); } return 0;}