#include<iostream>
using namespace std;

int graph[6][6];
bool visited[6];
int n = 6;

void dfs(int u) {
	visited[u] = true;
	cout << u << " ";
	for (int v = 0; v < n; v++) {
		if (graph[u][v] && !visited[v]) {
			dfs(v);
		}
	}
}
int main() {
	graph[0][1] = 1;
	graph[1][2] = 1;
	graph[1][3] = 4;
	graph[1][5] = 6;
	graph[2][3] = 1;
	graph[2][4] = 5;
	graph[3][4] = 3;
	graph[4][5] = 2;
	dfs(0);
}


//dji
#include<iostream>
using namespace std;

const int INF = 1e9;
int n = 6;
int src = 0;
int graph[6][6];
bool visited[6] = { false };
int dist[6];

int main() {
	for (int i = 0; i < n; i++) {
		dist[i] = INF;
		for (int j = 0; j < n; j++) {
			graph[i][j] = INF;
		}
	}
	dist[src] = 0;
	graph[0][1] = 1;
	graph[1][2] = 1;
	graph[1][3] = 4;
	graph[1][5] = 6;
	graph[2][3] = 1;
	graph[2][4] = 5;
	graph[3][4] = 3;
	graph[4][5] = 2;

	for (int i = 0; i < n; i++) {
		int u = -1;
		for (int j = 0; j < n; j++) {
			if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
				u = j;
			}
		}
		if (u == -1) break;
		visited[u] = true;
		for (int v = 0; v < n; v++) {
			if (graph[u][v] < INF && dist[u] + graph[u][v] < dist[v]) {
				dist[v] = dist[u] + graph[u][v];
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << dist[i] << " ";
	}
	return 0;
}


//快
#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);
    cout << "排序后: ";
    for (int num : arr) cout << num << " ";
    cout << endl;
    return 0;
} 




//区间调度
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<pair<int, int>> activities = {
       {1,4}, {3,5}, {0,6}, {5,7}, {8,9}
    };
    // 按 finish 升序排序
    sort(activities.begin(), activities.end(),
        [](auto& a, auto& b) { return a.second < b.second; });

    int count = 0, last_end = 0;
    for (auto& act : activities) {
        int s = act.first, f = act.second;
        if (s >= last_end) {
            cout << act.first << " - " << act.second << "  ";
            count++;
            last_end = f;
        }
    }
    cout << "Total interval: " << count << '\n';
    return 0;
}




//权最小prim
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minKey(const vector<int>& key, const vector<bool>& mstSet, int V) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v], min_index = v;
        }
    }
    return min_index;
}

void primMST(const vector<vector<int>>& graph) {
    int V = graph.size();
    vector<int> parent(V);
    vector<int> key(V, INT_MAX);
    vector<bool> mstSet(V, false);
    key[0] = 0;
    parent[0] = -1;
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    cout << "Edge\tWeight" << endl;
    for (int i = 1; i < V; i++)
        cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << endl;
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 3, 0},
        {2, 0, 1, 4},
        {3, 1, 0, 5},
        {0, 4, 5, 0}
    };
    primMST(graph);
    return 0;
} 


//key和频率，代价最小：OBST
#include <iostream>
#include <climits>
using namespace std;

int cost[100][100];

int sum(int freq[], int i, int j) {
    int s = 0;
    for (int k = i; k <= j; k++)
        s += freq[k];
    return s;
}

int OBST(int key[], int freq[], int n) {
    for (int i = 0; i < n; i++)
        cost[i][i] = freq[i];

    for (int L = 2; L <= n; L++) {
        for (int i = 0; i <= n - L; i++) {
            int j = i + L - 1;
            cost[i][j] = INT_MAX;

            for (int r = i; r <= j; r++) {
                int left = (r > i) ? cost[i][r - 1] : 0;
                int right = (r < j) ? cost[r + 1][j] : 0;
                int total_cost = left + right + sum(freq, i, j);

                if (total_cost < cost[i][j])
                    cost[i][j] = total_cost;
            }
        }
    }

    return cost[0][n - 1];
}

int main() {
    int key[] = {10, 20, 30, 40};
    int freq[] = {4, 2, 6, 3};
    int n = 4;

    cout << "Minimum cost of OBST is: " << OBST(key, freq, n) << endl;
    return 0;
}

//背包
#include<iostream>
using namespace std;

int main() {
	int wt[5] = { 0,1,3,4,5 };
	int val[5] = { 0,1,4,5,7 };
	int n = 4; int m = 7;
	int dp[5][8] = { 0 };

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j >= wt[i]) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - wt[i]] + val[i]);
			}
		}
	}
	cout << dp[4][7] << endl;//yes,9

	int i = 4, j = 7;
	while (i > 0) {
		if (dp[i][j] == dp[i - 1][j - wt[i]] + val[i]) {
			dp[i][j] -= val[i];
			cout << i << " 1" << endl;
			j -= wt[i];
			i--;
		}
		else
		{
			cout << i << " 0" << endl;
			i--;
		}
	}
}
//矩阵
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

void matrixChainOrder(const vector<int>& p) {
    int n = p.size() - 1;
    vector<vector<int>> m(n, vector<int>(n, 0));
    for (int L = 2; L <= n; L++) {
        for (int i = 0; i < n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }
    cout << "Minimum multiplication cost: " << m[0][n - 1] << endl;

}

int main() {
    vector<int> p = {10, 30, 5, 60, 10};
    matrixChainOrder(p);
    return 0;
} 


//LCS
#include<iostream>
#include<string>
using namespace std;

int main() {
	string s1 = "Stone";
	string s2 = "Longest";
	int m = s1.size();
	int n = s2.size();
	int dp[100][100] = { 0 };
	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (s1[i] == s2[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else
			{
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
			}
		}
	}
	cout << dp[m][n] << endl;

	int i = m, j = n;
	string res = "";
	while (i > 0 && j > 0) {
		if (dp[i][j] == dp[i - 1][j]) i--;
		else if(dp[i][j] == dp[i][j - 1]) j--;
		else
		{
			res += s1[i-1];//他妈的，这是index，也就是第i个字母，要-1
			i--;
			j--;
		}
	}
	reverse(res.begin(), res.end());
	cout << res << endl;
}

//装配线
#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <string> 
#include <cmath> 
using namespace std; 

int main() 
{ 
    const int n=4;
    int a[2][4]={3,5,2,4
               ,2,4,3,6};
    int t[2][3]={0,2,1,
                0,1,3};
    int e[2]={2,3};
    int x[2]={4,2};

    int f[2][n];
    int l[2][n];

    f[0][0]=a[0][1]+e[0];
    f[1][0]=a[1][1]+e[1];

    for (int i = 1; i < n; i++)
    {
        if (f[0][i-1]+a[0][i]<=f[1][i-1]+a[0][i]+t[1][i])
        {
            f[0][i]=f[0][i-1]+a[0][i];
            l[0][i]=0;
        }
        else
        {
            f[0][i]=f[1][i-1]+a[0][i]+t[1][i];
            l[0][i]=1;
        }
        if (f[1][i-1]+a[1][i]<=f[0][i-1]+a[1][i]+t[0][i])
        {
            f[1][i]=f[1][i-1]+a[1][i];
            l[1][i]=1;
        }
        else
        {
            f[1][i]=f[0][i-1]+a[1][i]+t[0][i];
            l[1][i]=0;
        }

    }
    int time,last_line;

    if(f[0][n-1]+x[0]<=f[1][n-1]+x[1])
    {
        time=f[0][n-1]+x[0];
        last_line=0;
    }
    else
    {
        time=f[1][n-1]+x[1];
        last_line=1;
    }

    cout<<"The minimum time is "<<time<<endl;
    cout<<"The last line is "<<last_line+1<<endl;
   
    vector<int> path(n);
    path[n-1]=last_line;
    for(int i=n-2;i>=0;--i){
        path[i]=l[path[i+1]][i+1];//用l[path[i+1]][i+1]来确定上一站的线
    }
    for(int i=0;i<n;++i){
        cout<<path[i]+1<<" ";
    }
    cout<<endl;

    return 0;
    
}