Faits: A. La loi fédérale du 13 juin 2008 sur le nouveau régime de financement des soins (RO 2009 3517), entrée en vigueur le 1er janvier 2011, a notamment complété la loi fédérale du 18 mars 1994 sur l'assurance-maladie (LAMal; RS 832.10) d'un nouvel art. 25a, dont l'alinéa 5 prévoit que: "Les coûts des soins [en cas de maladie] qui ne sont pas pris en charge par les assurances sociales ne peuvent être répercutés sur la personne assurée qu'à hauteur de 20% au plus de la contribution maximale fixée par le Conseil fédéral. Les cantons règlent le financement résiduel". L'ordonnance du Département fédéral de l'intérieur du 29 septembre 1995 sur les prestations dans l'assurance obligatoire des soins en cas de maladie (OPAS; RS 832.112.31) fixe les tarifs journaliers des soins dispensés dans un établissement socio-médical (ci-après: EMS) que l'assurance-maladie prend à sa charge. Cette participation varie entre 9 fr., pour un maximum de 20 minutes de soins par jour, et 108 fr., pour plus de 220 minutes de soins requis (art. 7a al. 3 OPAS). B. Le 21 février 2011, le Conseil d'Etat de la République et canton de Neuchâtel (ci-après: le Conseil d'Etat) a adopté un "Arrêté fixant les tarifs des soins de longue durée au sens de l'art. 25a LAMal dispensés en établissement médico-social (EMS)" [ci-après: l'Arrêté], qui a été publié dans la Feuille officielle de la République et canton de Neuchâtel n° 8 du 25 février 2011 (FO 11/08) et aux termes duquel: "Art. 1: En application de l'art. 5 al. 1 et de l'art. 6 du [Règlement provisoire], les tarifs journaliers des soins de longue durée, qui comprennent la part à charge des résidents ainsi que celle à charge de l'Etat, sont fixés dans l'annexe au présent arrêté. Art. 2 1: Le présent arrêté, qui entre en vigueur de manière rétroactive au 1er janvier 2011, est valable jusqu'au 31 décembre 2011 (...)". L'annexe à l'Arrêté prévoit: Financement des soins de longue durée - année 2011 Degré OPAS Degré PLAISIR Minutes de soins requises Part à charge des assureurs-maladie Part à charge des résidents Parts à EMS sans CGT d'association charge du EMS appliquant les CGT ANIPPA canton EMS appliquant les CCT santé 21 Coûts EMS sans CGT d'association EMS appliquant les CGT ANIPPA complets EMS appliquant la CCT santé 21 A 1 20] 9 [fr.] 0 0 0 0 0.6 9 9 9 9.6 B 2 ]20-40] 18 18 7.8 0 0 3 25.8 25.8 28.8 C 3 ]40-60] 27 16 0 0 5 43 43 48 D 4 ]60-80] 36 21.6 0 0 0 9.7 57.6 57.6 67.3 E 5 ]80-100] 45 21.6 0 0 0.3 19.9 66.6 66.9 86.5 F 6 ]100-120] 54 21.6 21.6 21.6 6.1 30.1 76.5 81.7 105.7 G 7 ]120-140] 63 21.6 21.6 5.8 12 40.3 90.4 96.6 124.9 H 8 ]140-160] 72 21.6 10.7 17.9 50.6 104.3 111.5 144.2 I 9 ]160-180] 81 21.6 15.6 23.8 60.8 118.2 126.4 163.4 J 10 ]180-200] 90 21.6 20.5 29.6 71 132.1 141.2 182.6 K 11 ]200-220] 99 21.6 25.5 35.5 81.3 146.1 156.1 201.9 L 12 ]220 108 21.6 12a ]220-240] 30.4 41.4 91.5 160 171 221.1 12b ]240-260] 44.3 56.2 110.7 173.9 185.8 240.3 12c ]260-280] 58.2 71.1 130 187.8 200.7 259.6 12d ]280-300] 72.1 86 149.2 201.7 215.6 278.8 12e ]300 0.69 0.74 0.96 Classes 1 à 12, ainsi que 12a à 12d: tarifs journaliers / Classe 12e: tarifs pour une minute de soins requis. Cet arrêté possède un caractère transitoire, car son expiration est fixée au 31 décembre 2011. Il a été adopté sur la base du Règlement provisoire d'introduction de la loi fédérale du 13 juin 2008 sur le nouveau régime de financement des soins (ci-après: le Règlement provisoire), à teneur duquel: "Art. 4 1 En cas de séjour dans un EMS admis à pratiquer à la charge de l'assurance obligatoire des soins, la part du coût des soins de longue durée incombant au résident correspond à la différence entre le coût du niveau de soins requis fixé par le Conseil d'Etat et la part de ce coût qui est prise en charge par l'assurance obligatoire des soins, mais au plus à 20% de la contribution maximale fixée par le Conseil fédéral (part du résident). 2 La part du coût des soins qui n'est pas prise en charge par les assurances sociales ou par le résident incombe à l'Etat (part cantonale) [...]. Art. 6 1 Le Conseil d'Etat fixe pour l'année 2011, par voie d'arrêté, la part cantonale au sens de l'art. 4 al. 2. 2 Pour définir la part cantonale, le Conseil d'Etat: a) se base sur les informations comptables et statistiques de l'année 2009 fournies par les EMS; b) tient compte, dans le calcul du coût des soins, des frais de personnel soignant, à hauteur d'un taux de couverture des soins requis de 95%, les charges sociales ainsi que le petit matériel nécessaire à la fourniture de soins ne pouvant être imputé à un résident identifié; c) détermine le coût d'une minute de soins, en tenant compte d'une majoration de 1,5% correspondant à l'indexation et à l'augmentation de la masse salariale; d) calcule le coût journalier des soins par niveau de dépendance sur la base du poids moyen de chaque catégorie; e) soustrait du coût des soins les participations à charge du résident et de l'assureur-maladie (...). 5 L'application en 2011 par les EMS des CCT santé 21 donne droit à une majoration de la part cantonale. L'application en 2011 de conditions générales de travail (CGT) émises par une association professionnelle d'EMS, mais déjà en vigueur en 2009, donne également droit à une majoration de la part cantonale, cette dernière étant toutefois inférieure à celle due à l'application des CCT santé 21. 6 Si les tarifs fixés par le Conseil d'Etat mettent en péril la qualité des soins et la situation financière d'un EMS, le département peut, à la demande de l'EMS, fixer une part cantonale plus élevée pour une durée déterminée (...)". Cette réglementation provisoire, édictée par le Conseil d'Etat le 15 décembre 2010, a été mise en place parce que la base légale cantonale prévue, à savoir la loi cantonale du 28 septembre 2010 sur le financement des établissements médico-sociaux (LFinEMS/NE), avait fait l'objet d'une demande de référendum. Elle ne pouvait donc entrer en vigueur le 1er janvier 2011, de sorte que le canton de Neuchâtel se devait, pour respecter les exigences du nouvel art. 25a al. 5 LAMal, de prévoir un mode de financement pour la part résiduelle mise à leur charge. C. Le 28 mars 2011, A._ Sàrl, B._ SA, C._ SA, D._ SA, E._, F._, et G._ SA, étant tous des entreprises individuelles ou sociétés exploitant des établissements médico-sociaux dans le canton de Neuchâtel, ont déposé un recours en matière de droit public au Tribunal fédéral à l'encontre de l'Arrêté du 21 février 2011. Ils concluent à son annulation, subsidiairement à l'annulation de son article premier et des montants figurant dans l'annexe fixant les parts à charge du canton et les coûts complets. Ils se plaignent en particulier d'une violation de l'art. 25a LAMal, de la loi fédérale du 28 septembre 1956 permettant d'étendre le champ d'application de la convention collective de travail (LECCT; RS 221.215.311), du principe de la séparation des pouvoirs, ainsi que des art. 8, 9, 23, 27, 28, 94 et 110 Cst. Le Conseil d'Etat conclut, sous suite de frais, au rejet du recours. L'Office fédéral de la santé publique a renoncé à se déterminer. A la suite d'un échange de vues entre les présidents de la IIe Cour de droit social et de la IIe Cour de droit public, la cause sera traitée par la seconde sous le numéro 2C_728/2011. Le 23 décembre 2011, la Cour de céans a délibéré sur le recours en séance publique.