程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj-1699-Best Sequence-dfs+子狀態

poj-1699-Best Sequence-dfs+子狀態

編輯:C++入門知識

這道題目竟然真的ac了,好神奇啊。

當時算的時間復雜度為O(T*N!),理論值達到7kw。

做法:

預處理dp數組,使得dp[i][j]代表j放在i後面長度的增加值。

然後dfs,dfs的時候要注意,用一個二進制數標記當前狀態。

二進制中0代表當前位置已取,1代表當前位置未取。每次查找二進制的子狀態。

然後看看哪個位置在子狀態消失了。

一定要直接查找子狀態。

 

#include
#include
#include
#include
using namespace std;
char str[31][31];
int dp[31][31];
int vis[31];
int n;
int ans;
int fc[(1<<21)];
int houji(int x,int y)
{
    int i,j;
    int len1=strlen(str[x]);
    int len2=strlen(str[y]);
    for(i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved